Historia kościoła przy ulicy Wolskiej 76 sięga 21 grudnia 1885 roku, kiedy to Szymon Ołdak na mocy darowizny podarował swoją parcelę pod budowę nowej świątyni. W dniu 26 czerwca nastąpiło uroczyste poświęcenie i położenie pierwszej cegły pod budowę nowego kościoła przez metropolitę warszawskiego, arcybiskupa Wincentego Chościaka Popiela. Świątynia została zaprojektowana przez Józefa Piusa Dziekońskiego w stylu neogotyckim, a wzniesiona na planie krzyża łacińskiego. Od południa została wybudowana wieża zwieńczona ośmiobocznym hełmem z czterema wieżyczkami w narożnikach. W dniu 8 grudnia 1903 roku nastąpiło poświęcenie kościoła przez księdza prałata Zygmunta Łubińskiego. W dniu 15 czerwca 1925 roku w kościele wybuchł pożar, podczas którego spłonęły organy i wieża. 1 kwietnia 1927 roku erygowana została parafia pod wezwaniem św. Wojciecha. We wrześniu 1939 roku, w czasie okupacji niemieckiej, został uszkodzony dach kościoła, wieża, organy oraz witraże. W czasie powstania warszawskiego na terenie kościoła hitlerowcy urządzili obóz przejściowy dla deportowanych mieszkańców Warszawy. Stąd ludność cywilna była prowadzona na Dworzec Zachodni, a następnie przewożona do stacji Warszawa-Włochy i stamtąd do obozu w Pruszkowie. W dniu 8 sierpnia 1944 roku zostali rozstrzelani dwaj wikariusze, Stanisław Mączka i Stanisław Kulesza, oraz rezydent ksiądz Roman Ciesiołkiewicz. Po II wojnie światowej kościół został odbudowany i wyremontowany. W 1997 roku do świątyni zostały sprowadzone relikwie św. Wojciecha.