This study was designed to investigate associations among five factor personality traits, perceived stress, and depressive symptoms and to examine the roles of personality and perceived stress in the relationship between gender and depressive symptoms. The participants (N = 3,950) were part of a cohort study for health screening and examination at the Kangbuk Samsung Hospital. Personality was measured with the Revised NEO Personality Inventory (NEO-PI-R). Depressive symptoms were assessed using the Center for Epidemiologic Studies Depression Scale (CES-D). Perceived stress level was evaluated with a self-reported stress questionnaire developed for the Korea National Health and Nutrition Examination Survey. A higher degree of neuroticism and lower degrees of extraversion, agreeableness, and conscientiousness were significantly associated with greater perceived stress and depressive symptoms. Neuroticism and extraversion had significant direct and indirect effects (via stress as a mediator) on depressive symptoms in both genders. Agreeableness and conscientiousness had indirect effects on depression symptoms in both genders. Multiple mediation models were used to examine the mediational roles of each personality factor and perceived stress in the link between gender and depressive symptoms. Four of the personality factors (except openness) were significant mediators, along with stress, on the relationship between gender and depressive symptoms. Our findings suggest that the links between personality factors and depressive symptoms are mediated by perceived stress. As such, personality is an important factor to consider when examining the link between gender and depression.