Common mental disorders (CMD), such as depression and anxiety disorders that affect mothers with young children, are a major public health issue in developing countries. This study investigates the prevalence of CMD and its associated factors among mothers attending a well-child clinic in Mombasa, Kenya. In this cross-sectional study, 429 women were screened for the presence of CMD using the Self-Reporting Questionnaire–20 (SRQ-20). Social support and social stress were measured using the OSLO Social Support Scale and the Life Events Checklist. The prevalence of CMD was 20%. High SRQ scorers were more likely to be single or separated/divorced compared with low scorers. Language, neighborhood, and financial difficulties were found to be significant independent correlates of CMD through multiple logistic regression analysis. Rates of CMD among mothers with young children in Kenya are high. This is important for nurses and pediatricians whose contact offers them an opportunity to detect CMD and refer mothers for appropriate support.