Background: Timely decision making is crucial for survival and reproduction. Organisms often face a speed-accuracy tradeoff, as fully informed, accurate decisions require time-consuming gathering and treatment of information. Optimal strategies for decision-making should therefore vary depending on the context. In mammals, there is mounting evidence that multiple systems of perceptual discrimination based on different neural circuits emphasize either fast responses or accurate treatment of stimuli depending on the context. Methodology/Principal Findings: We used the ant Camponotus aethiops to test the prediction that fast information processing achieved through direct neural pathways should be favored in situations where quick reactions are adaptive. Social insects discriminate readily between harmless group-members and dangerous strangers using easily accessible cuticular hydrocarbons as nestmate recognition cues. We show that i) tethered ants display rapid aggressive reactions upon presentation of non-nestmate odor (120 to 160 ms); ii) ants' aggressiveness towards non-nestmates can be specifically reduced by exposure to non-nestmate odor only, showing that social interactions are not required to alter responses towards non-nestmates; iii) decision-making by ants does not require information transfer between brain hemispheres, but relies on side-specific decision rules. Conclusions/Significance: Our results strongly suggest that first-order olfactory processing centers (up to the antennal lobes) are likely to play a key role in ant nestmate recognition. We hypothesize that the coarse level of discrimination achieved in the antennal lobes early in odor processing provides enough information to determine appropriate behavioral responses towards non-nestmates. This asks for a reappraisal of the mechanisms underlying social recognition in insects.