Users in social networking sites, such as Facebook, are increasingly receiving friend requests from strangers. This study examines the effects of the Big Five personality traits (Neurotics vs. Extroversion vs. Openness vs. Conscientiousness vs. Agreeableness) and strangers’ gender in affecting Facebook users’ decisions to accept (or ignore) the stranger’s friend request. Results showed that gender of the stranger and the personality match between participant and stranger jointly affect the decision to accept the stranger as friend on Facebook. Most of the participants accepted the stranger’s friend request based on textual cues that were displayed in the friend request message. This finding supported Social Information Processing theory, suggesting that impression formation of the stranger was not constrained to the lack of nonverbal cues online. Moreover, participants were more likely to accept the stranger’s friend request when the participant’s and stranger’s personalities matched. This effect was more pronounced when the stranger was a female. Participants accepted female stranger’s friend request due to the inflated perception of stereotypical female characteristics, which supports the Hyperpersonal Perspective.