Szykowana na następczynię Anny Streżyńskiej, czyli na nową szefową Urzędu Komunikacji Elektronicznej, Magdalena Gaj urodziła się w Chełmie w 1974 r. Tam też w 1993 r. skończyła liceum w klasie o profilu biologiczno-chemicznym. Pięć lat później obroniła się na Wydziale Prawa Uniwersytetu Marii Curie-Skłodowskiej w Lublinie. W latach 1998 – 2002 w tym samym mieście odbyła aplikację radcowską przy Okręgowej Izbie Radców Prawnych.
Pod koniec tego etapu (2001 – 2009) zaczęła pracę w UKE. Była tu również bliskim współpracownikiem Streżyńskiej: prowadziła Departament Prawny.
W 2009 r. premier powołał ją na podsekretarza stanu w Ministerstwie Infrastruktury, gdzie do jej kompetencji należało m.in. dostosowanie prawa telekomunikacyjnego do regulacji unijnych oraz cyfryzacja kraju. Rozpoczęła m.in. proces przejścia Polski z telewizji analogowej na naziemną telewizję cyfrową.
Po podziale resortu infrastruktury pod koniec 2011 roku Gaj trafiła pod skrzydła ministra cyfryzacji i administracji Michała Boniego. W MAiC odpowiada nadal za Departament Telekomunikacji i Poczty.
Jeszcze w resorcie infrastruktury jej pomysłem był m.in. projekt oddłużający operatorów komórkowych i dlatego też przez większość z nich popierany. Zakładał zamianę blisko 1 mld zł zobowiązań licencyjnych komórkowców (wynikających z rozłożonej na raty płatności za częstotliwości UMTS) na inwestycje, w tym zakup komputerów dla uczniów. Wypłynął na krótko przed wyborami parlamentarnymi i na razie nie znalazł szczęśliwego finału.