Humans are fast and accurate in categorizing faces among other objects in natural scenes. While the configurations among face exemplars are highly similar, faces may appear rather differently due to visual variations, such as changes in head orientation and eye gaze. We wonder whether there is a cost to generalize across these visual differences for accomplishing face categorization. The effects of head orientation and perceived gaze direction on face categorization were investigated using a rapid serial visual presentation (RSVP) approach. Observers (N=19) were presented with 15,491 unsegmented natural images (350 faces, 15,141 non-face objects) randomly in rapid succession (SOA=91.7 ms), and were instructed to respond immediately to every face. Faces differed in gaze and head orientation in 7 combinations (50 faces/combination; presented randomly throughout the sequence): Full-front views with (1) direct gaze, (2) left-averted gaze, or (3) right-averted gaze; Left ¾ side views with (4) direct gaze, or (5) averted gaze; and Right ¾ side views with (6) direct gaze, or (7) averted gaze. We found highly accurate responses to faces (95% correct). Crucially, both perceived gaze direction and head orientation had comparable, significant, and non-interactive effects on response time (RT), where responses to direct gaze were faster than to averted gaze by 48 ms, and responses to full-front view faster than to ¾ side view also by 48 ms. Full-front faces with direct gaze (RT=454 ms) led to an additive speed advantage (96 ms) to ¾ faces with averted gaze (RT=550 ms). We found no significant RT differences between left and right gaze aversions, or between left and right ¾ side views. The results suggest that the effects of perceived gaze direction and head orientation on the speed of face categorization depend on the degree of social relevance of the face to the viewer.