Mary Eliza Mahoney werd in 1845 geboren in Dorchester, Massachusetts. Mahoney’s ouders waren bevrijde slaven, oorspronkelijk uit North Carolina, die voor de Amerikaanse Burgeroorlog naar het noorden waren getrokken op zoek naar een leven met minder rassendiscriminatie. Mahoney was de oudste van twee kinderen; een van zijn broers en zussen stierf al vroeg als kind. Al op jonge leeftijd was Mahoney een toegewijd baptist en kerkganger die vaak de People’s Baptist Church in Roxbury bezocht. Mahoney werd op 10-jarige leeftijd toegelaten tot de Phillips School, een van de eerste geïntegreerde scholen in Boston, en bleef er van de eerste tot de vierde klas. De Phillips School stond bekend om het onderwijzen van moraal en menselijkheid, naast algemene vakken als Engels, Geschiedenis, Rekenen, en meer. Er wordt gezegd dat dit onderwijs van invloed is geweest op Mahoney’s vroege belangstelling voor de verpleegkunde.
Mahoney wist al vroeg dat ze verpleegster wilde worden; mogelijk omdat er tijdens de Amerikaanse Burgeroorlog al verpleegsters in opkomst waren. Zwarte vrouwen hadden het in de 19e eeuw vaak moeilijk om opgeleid en gediplomeerd verpleegster te worden. Verpleegstersopleidingen in het Zuiden wezen aanvragen van Afro-Amerikaanse vrouwen af, terwijl Afro-Amerikanen in het Noorden, hoewel de mogelijkheden nog steeds zeer beperkt waren, een grotere kans hadden op toelating tot opleidingen en afgestudeerde programma’s. Zodra het New England Hospital for Women and Children was opgericht, begon zij op 18-jarige leeftijd belangstelling te tonen voor verpleegkunde. Het NEHWC werd de eerste instelling die een programma aanbood dat vrouwen de mogelijkheid bood om toe te treden tot de gezondheidszorg, die voornamelijk door mannen werd geleid. In 1878 werd zij op 33-jarige leeftijd, samen met 39 andere studenten, toegelaten tot een 16 maanden durend programma in het New England Hospital for Women and Children (nu het Dimock Community Health Center). Haar zuster, Ellen Mahoney, besloot ook aan dezelfde verpleegstersopleiding deel te nemen, maar slaagde er niet in haar diploma te behalen. De criteria die het ziekenhuis hanteerde bij het kiezen van studenten voor hun opleiding benadrukten dat de 40 kandidaten “gezond en sterk, tussen de 21 en 31 jaar oud, en een goede reputatie wat betreft karakter en aanleg” moesten zijn. Uit een klas van 40 studenten waren zij en twee andere blanke vrouwen de enigen die hun diploma kregen. Aangenomen wordt dat de administratie Mahoney aanvaardde, ondanks het feit dat zij niet aan de leeftijdscriteria voldeed, vanwege haar banden met het ziekenhuis door haar vroegere werk als kok, dienstmeisje en wasvrouw toen zij 18 jaar oud was. Mahoney werkte bijna 16 uur per dag gedurende de 15 jaar dat zij als werkster werkte.
Mahoney’s opleiding vereiste dat zij ten minste een jaar op de verschillende afdelingen van het ziekenhuis doorbracht om universele verpleegkundige kennis op te doen. Het werk binnen de opleiding was intensief en bestond uit lange dagen met een dienst van 5.30 uur tot 21.30 uur, waarbij Mahoney lezingen en lessen moest bijwonen om zichzelf te onderrichten aan de hand van instructies van artsen op de afdeling. Deze 12 uur durende colleges bestonden uit verpleging in gezinnen, fysiologische vakken, voeding voor zieken, chirurgische verpleging, kinderbedverpleging, ontsmettingsmiddelen en algemene verpleging. Buiten de colleges om leerden de studenten veel belangrijke procedures aan het bed, zoals het opnemen van vitale functies en het verbinden. Bovendien werkte Mahoney enkele maanden als verpleegster in een privé-dienst. Het verpleegprogramma bood de studenten de mogelijkheid om na hun eerste twee weken werk een weekloon te verdienen, variërend van 1 tot 4 dollar. Veel verpleegsters zagen het weekloon niet als belangrijk, aangezien velen van hen het financieel moeilijk hadden en dus 25% van hun loon teruggaven voor financiële hulp aan het ziekenhuis. Driekwart van het programma bestond uit verpleegkundigen die op een chirurgische, kraam- of medische afdeling werkten met zes patiënten voor wie zij verantwoordelijk waren. De laatste twee maanden van het 16 maanden durende programma moesten de verpleegsters hun nieuwe kennis en vaardigheden toepassen in omgevingen die ze niet gewend waren, zoals ziekenhuizen of privégezinnen. Na deze eisen te hebben vervuld, studeerde Mahoney in 1879 af als gediplomeerd verpleegster, samen met 3 andere collega’s – de eerste zwarte vrouw in de Verenigde Staten.