Parafia św. Marii Magdaleny na Bródnie swoje początki ma w okresie międzywojennym. Została powołana 1 marca 1939 r. na terenie Annopola, który tworzył zespół baraków schroniska dla bezrobotnych i bezdomnych. Świątynią parafii była kaplica, która uległa zniszczeniu w czasie II wojny światowej wraz z częścią zabudowań schroniska. Działalność parafii zawieszono w kwietniu 1945 r. ze względu na znaczący spadek liczby wiernych.
Kiedy w latach 70. zaczęła się urbanizacja Bródna, która spowodowała napływ nowych mieszkańców, zaczęto starania o reaktywację parafii z Annopola zakończone ponownym jej erygowaniem przez Prymasa Polski kard. Stefana Wyszyńskiego w 1980 r. W 1979 r. ks. Romuald Gawlik, proboszcz parafii, otrzymał zgodę na budowę kościoła przy ulicy Echa Leśne w części Bródna zwanej Ugorami. W 1980 r. wmurowano kamień węgielny, a budowę zakończono w 1989.
Nową świątynię konsekrował 9 maja tego roku kard. Józef Glemp. Autorami projektu dwupoziomowego kościoła byli architekci Ryszard Trzaska i Janusz Olszewski. W ołtarzu wyróżnia się krzyż autorstwa rzeźbiarza Jerzego Machaja nazywanego „artystą od krzyży”.