Mary Eliza Mahoney urodziła się w 1845 roku w Dorchester, Massachusetts. Rodzice Mahoney byli wyzwolonymi niewolnikami, pochodzącymi z Karoliny Północnej, którzy przenieśli się na północ przed amerykańską wojną secesyjną w poszukiwaniu życia w warunkach mniejszej dyskryminacji rasowej. Mahoney był starszym z dwójki dzieci; jedno z rodzeństwa zmarło we wczesnym dzieciństwie. W młodym wieku Mahoney był gorliwym baptystą i bywalcem kościołów, który często uczęszczał do People’s Baptist Church w Roxbury. W wieku 10 lat Mahoney został przyjęty do Phillips School, jednej z pierwszych zintegrowanych szkół w Bostonie, gdzie uczęszczał od pierwszej do czwartej klasy. Phillips School była znana z nauczania uczniów wartości moralności i człowieczeństwa, obok przedmiotów ogólnych, takich jak angielski, historia, arytmetyka i inne. Mówi się, że to nauczanie wpłynęło na wczesne zainteresowanie Mahoney pielęgniarstwem.
Mahoney od początku wiedziała, że chce zostać pielęgniarką; prawdopodobnie z powodu natychmiastowego pojawienia się pielęgniarek podczas amerykańskiej wojny secesyjnej. Czarne kobiety w 19 wieku często miały trudny czas stania się wyszkolonymi i licencjonowanymi pielęgniarkami. Szkoły pielęgniarskie na Południu odrzucały podania Afroamerykanek, podczas gdy na Północy, choć możliwości były nadal mocno ograniczone, Afroamerykanki miały większe szanse na przyjęcie na szkolenia i programy dyplomowe. Gdy tylko powstał New England Hospital for Women and Children, w wieku 18 lat zaczęła przejawiać zainteresowanie pielęgniarstwem. NEHWC stał się pierwszą instytucją, która zaoferowała program umożliwiający kobietom podjęcie pracy w służbie zdrowia, która była w przeważającej mierze prowadzona przez mężczyzn. W 1878 roku została przyjęta do 16-miesięcznego programu w New England Hospital for Women and Children (obecnie Dimock Community Health Center) w wieku 33 lat, wraz z 39 innymi studentami. Jej siostra, Ellen Mahoney, również zdecydowała się uczęszczać na ten sam program pielęgniarski, ale nie udało jej się otrzymać dyplomu. Kryteria, które szpital zastosował przy wyborze studentów do swojego programu, podkreślały, że 40 kandydatów powinno być „zdrowych i silnych, w wieku od 21 do 31 lat, i mieć dobrą reputację co do charakteru i usposobienia”. Z klasy 40 studentów, ona i dwie inne białe kobiety były jedynymi, które otrzymały dyplom. Przypuszcza się, że administracja zaakceptowała Mahoney, mimo że nie spełniała kryteriów wiekowych, ze względu na jej związek ze szpitalem poprzez wcześniejszą pracę jako kucharka, pokojówka i praczka, kiedy miała 18 lat. Mahoney pracowała prawie 16 godzin dziennie przez 15 lat, kiedy pracowała jako laborantka.
Szkolenie Mahoney wymagało od niej spędzenia co najmniej jednego roku na różnych oddziałach szpitala w celu zdobycia uniwersalnej wiedzy pielęgniarskiej. Praca w ramach programu była intensywna i składała się z długich dni na zmianie od 5:30 rano do 9:30 wieczorem, co wymagało od Mahoney uczęszczania na wykłady i lekcje, aby kształcić się poprzez instrukcje lekarzy na oddziale. Te 12-godzinne wykłady obejmowały pielęgniarstwo rodzinne, przedmioty fizjologiczne, jedzenie dla chorych, pielęgniarstwo chirurgiczne, pielęgniarstwo dziecięce, środki dezynfekujące i pielęgniarstwo ogólne. Poza wykładami, studenci uczyli się wielu ważnych procedur przyłóżkowych, takich jak przyjmowanie oznak życia i bandażowanie. Ponadto Mahoney przez kilka miesięcy pracowała jako pielęgniarka na prywatnym dyżurze. Program pielęgniarski pozwalał studentom zarabiać tygodniową pensję, wahającą się od 1 do 4 dolarów, po pierwszych dwóch tygodniach pracy. Wiele pielęgniarek nie uważało tygodniowych zarobków za znaczące, ponieważ wiele z nich borykało się z problemami finansowymi i w związku z tym oddawało 25% swoich zarobków na pomoc finansową dla szpitala. Trzy czwarte programu polegało na pracy pielęgniarek na oddziale chirurgicznym, położniczym lub medycznym z sześcioma pacjentami, którymi się opiekowały. Ostatnie dwa miesiące rozległego 16-miesięcznego programu wymagały od pielęgniarek wykorzystania ich nowo nabytej wiedzy i umiejętności w środowiskach, do których nie były przyzwyczajone, takich jak szpitale czy prywatne domy rodzinne.Po spełnieniu tych wymagań Mahoney ukończyła studia w 1879 roku jako zarejestrowana pielęgniarka wraz z 3 innymi koleżankami – była pierwszą czarną kobietą, która zrobiła to w Stanach Zjednoczonych.