Z części parafii Chrystusa Króla na Targówku, oraz części parafii Matki Bożej Różańcowej na Bródnie, mocą dekretu wydanego przez Stefana Kardynała Wyszyńskiego utworzona została nowa parafia pw. Św. Wincentego a Paulo. Wydarzenie to miało miejsce 1 września 1952 roku. Pierwszym proboszczem mianowany został Ks. Zdzisław Waś. Z terenu Cmentarza Bródzieńskiego wydzielona została niewielka działka budowlana. Duszpasterze przy znaczącym wsparciu parafian rozpoczęli starania o wydanie zgody na budowę nowego kościoła i plebanii. Ich starania uwieńczone został sukcesem. Wymaganą zgodę lokalizacyjną i budowlaną uzyskano. Po poświeceniu fundamentów przez Stefana Kardynała Wyszyńskiego, a miało to miejsce 13 lipca 1957 roku, przystąpiono do budowy świątyni zaprojektowanej przez inż. Arch. Stanisława Marzyńskiego. Zgodnie z ustaleniami z 1952 roku miała to być replika kaplicy- mauzoleum hr. Przeździeckich, ufundowanej dla parafii Św. Barbary na Koszykach pod koniec XIX wieku. Była to budowla imitująca gotyk z kamiennymi rzeźbami. W czasie działań wojennych 1939 roku kaplica w znaczącym stopniu uległa zniszczeniu. Ocalały jedynie jej nieliczne elementy, które przewiezione zostały na Bródno i osadzone w analogicznych miejscach jak w oryginale. Wystarczyło to jedynie do zbudowania portalu nowowznoszonej świątyni.

Uroczystego poświęcenia kościoła, za patronkę, którego obrana została Matka Boża Częstochowska dokonał w dniu 24 sierpnia 1960 roku Biskup Wacław Majewski. W późniejszych latach dobudowane zostały przez Ks. proboszcza Stanisława Hermanowicza dwie boczne nawy. Zostały one poświęcone przez Biskupa Bronisława Dąbrowskiego dn. 2 lutego 1980 roku. Uroczystej konsekracji świątyni w dniu 22 września 1984 roku dokonał Prymas Polski Józef Kardynał Glemp.

Architektura nawy środkowej nawiązuje do gotyku- żebrowe sklepienie jest jednak mniej strzeliste, a łuki łagodniejsze. Budowa świątyni pochłonęła wszystkie zgromadzone na ten cel fundusze, toteż pierwotne jej wyposażenie było nader skromne. Gruntowna i zasadnicza modernizacja, wyposażenie i upiększenie wnętrza oraz zagospodarowanie terenu przy kościelnego rozpoczęto w roku 1994. Trzynawowe wnętrze kościoła, z kaplicą Zaśnięcia Najświętszej Maryi Pany, zakrystią i chórem zaprojektował profesor Akademii Sztuk Pięknych p. Kazimierz Zieliński. Wnętrze ubogacają nowe ołtarze wzorowane na gotyckich poświęcone przez Biskupa Kazimierza Romaniuka w 2001 roku. W ołtarzu głównym umieszczony został obraz Matki Bożej Częstochowskiej. "Czarna Madonna" z Jasnej Góry, Patronka świątyni, pozostaje dla wielu z nas najwierniejszą powierniczką naszych codziennych trosk. To na jej ręce składamy modlitwy i prośby o pomoc. Cierpliwie w modlitwie wyciąga ku nam swoją dłoń, by ukoić cierpiące serca i dusze. W ołtarzu Św. Jana Chrzciciela znajduje się tabernakulum z Najświętszym Sakramentem, natomiast w ołtarzu patrona parafii Św. Wincentego a Paulo znajdują się Jego relikwie. Na filarach kościoła umieszczono figury 4 - Ewangelistów oraz Św. Piotra i Św. Pawła. Na chórze zostały zbudowane nowe organy w latach 1996 - 2000. W lewej nawie bocznej znajduje się ołtarz Miłosierdzia Bożego z obrazem autorstwa p. Joanny Polaskiej i z relikwiami Św. siostry Faustyny i ołtarz Św. Michała Archanioła przy wejściu do zakrystii oraz Obrazy Matki Bożej Nieustającej Pomocy i Sługi Bożego Ojca Świętego Jana Pawła II. W prawej nawie natomiast zobaczyć można wspaniałą bogato rzeźbioną chrzcielnicę i ołtarz Św. Antoniego. W kruchcie kościoła powstała w 2005 roku kaplica Bożego Grobu. Wykonawcami wyposażenia wnętrza kościoła byli stolarze i rzeźbiarze z Mazowsza i Podhala p. Przemysław, Szczepan, Władysław, Andrzej i Aleksander. Polichromię w kaplicy Zaśnięcia NMP ze scenami z życia NMP zaprojektowała i wykonała warszawianka p. Joanna Polaska. Ona jest również autorem namalowanych w latach 1998-2001 sześciu obrazów olejnych przedstawiających sceny z Ewangelii , a wiszących obecnie w nawie głównej kościoła. Do wyposażenia kościoła należy zaliczyć: witraże w prezbiterium przedstawiające Papieża Jana pawła II oraz Prymasa Tysiąclecia Kardynała Stefana Wyszyńskiego, które zostały wykonane przez Pracownię Witraży p. Mirosława Spirowskiego z Otwocka według projektu artysty malarza p. Lecha Okołowa z Warszawy w 1993r.; witraże nawy głównej zaprojektowane i wykonane przez pracownię p. Andrzeja Skalskiego, witraż na chórze, przedstawiający głowę Chrystusa, a pochodzący z kaplicy - mauzoleum Przeździeckich, oraz witraże w nawach bocznych i zakrystiach z różnymi gatunkami ptaków, które w chrześcijaństwie mają swoje symboliczne znaczenie. Te ostatnie projektowała i wykonała pracownia p. Władyslawa Czyża z Lublina. Warto również wspomnieć o pięknych rzeźbionych w drewnie stacjach Drogi Krzyżowej wraz z płaskorzeźbą Zmartwychwstania zdobiących nawy boczne, które zostały zaprojektowane i wykonane przez artystę rzeźbiarza Jana Funka z Krakowa w latach 1988/89 i umieszczonych pięć neogotyckich konfesjonałów z płaskorzeźbą Chrystusa Dobrego Pasterza. W 2007 roku wymieniono główne drzwi kościoła, a 2008 roku stare ławki na nowe.

Przy parafii działają następujące współnoty: Wspólnota Żywego Różańca, Legion Maryi, Chór, Bielanki i Ministranci oraz Schola, oddział parafialnego Caritasu i sklepik parafialny Św. Wincentego a Paulo.