Converging evidence from behavioral, neural, and computational investigations has led to the theory that rapid scene categorization can be performed based on the extraction of simple features (e.g. oriented edges, colors, etc.) and does not necessarily require an organization of these features into coherent parts, objects, or surfaces. This is consistent with findings that many perceptual grouping tasks and image segmentation in general are computationally expensive processes requiring multiple iterations of feedback. Therefore, these grouping and segmentation processes must take place after scene category information has already been computed (a process assumed to be rapid and feedforward). In a series of three experiments, we questioned whether segmentation processes indeed did not play a role in the rapid scene categorization. In particular, if categorization were only based on feature extraction, with relations between features or objects playing only a minor role, segmentation cues should not influence categorization accuracy. If, however, categorization was also based on the relations between these features, misleading segmentation cues should impede categorization performance. In each trial, we presented participants with two scenes divided into four parts, using segmentation cues displayed for 300 ms prior to image onset. These cues established either a congruent (supporting the correct image segmentation into two scenes) or incongruent (pushing observers to incorrectly group scene segments) figure-ground segmentation on the display. We found that participants were less accurate in scene categorization when incongruent segmentation cues were presented, indicating that segmentation plays a role in rapid categorization decisions. Moreover, the effect remained robust even when the cues were presented concurrently with the images, suggesting that whilst scene categorization might be rapid, it also interacts with equally fast mechanisms of scene segmentation.