Sa mère, Elizabeth Draper, était une esclave affranchie au lendemain de la guerre civile qui a ensuite travaillé comme cuisinière pour Elizabeth Van Lew. Cette grande figure de la cause abolitionniste avait, pendant la guerre civile, mis en place un vaste réseau d’espionnage en Virginie au profit du Nord.
Le mystère demeure quant à la véritable identité du père de Maggie. Selon certains, il pourrait s’agir d’Eccles Cuthbert, journaliste d’origine irlandaise, correspondant du (New York Herald) à Richmond, et également ardent militant de la cause abolitionniste. Quoi qu’il en soit, Maggie Lena Walker ne le connaîtra jamais.
En 1868, un an après sa naissance, sa mère épousa William Mitchell, un mulâtre qui travaillait comme majordome pour Elizabeth Van Lew. Le couple a ensuite déménagé dans une maison non loin du domaine Van Lew qu’elle partageait avec plusieurs familles Noires/Africaines. Tandis que William Mitchell trouvait un emploi de majordome dans l’hôtel principal de Richmond, Elizabeth Draper s’installait comme femme de ménage.
Lorsqu’elle était adolescente, Maggie Mitchell a rejoint le conseil local de l’Ordre indépendant de Saint-Luc. Cette société funéraire fraternelle, créée en 1867 à Baltimore, s’occupait des malades et des personnes âgées, promouvait les causes humanitaires et encourageait la bienveillance et l’intégrité individuelles.