Traditia ne spune ca in trecut a existat o biserica din lemn a unui schit de maici, cu Hramul Cuvioasa Paraschiva, asezat intre albia cea mare a Dambovitei si firul de apa ce trecea prin spate, spre morile Manastirii Radu-Voda, aflate la circa 500 de metri distanta. Prima atestare cunoscuta este din anul 1642(?) de cand dateaza o insemnare iscalita de preotul Bunea, pe o carte de rugaciuni scrisa in slavoneste. Un "Bunea erei" este trecut intr-unul din pomelnicele lacasului. Unele documente ale bisericii mentioneaza ca aceasta ar fi avut si Hramurile sfantului Nicolae si sfanta Filofteia. In preajma acestui schit la miazanoapte pe la 1672-1673 prin hotararea domneasca, la initiativa unor boieri din Sfatul Domnesc, sunt mutati tabacarii sau tabacii din mahalaua Sarindarului. De la aceeasi tabaci provine numele mahalalei; la inceput enoria lor avea o singura biserica, Sfantul Nicolae "din Sarbi" (atestata la 1639 si cunoscuta in 1823, ca biserica din "Mahalaua tabacilor sarbi"(azi, demolata). Oricum, cea mai veche atestare sigura, a primului lacas, i-o datoram misionarului Blasius Kleiner care o pomeneste in lista sa de biserici bucurestene, intocmita ante 1761: "Apostol, din lemn". Biserica din zid pe care o vedem acum pe deal, a fost ctitorita, prin osteneala preotului Popa Constandinu si a sotiei sale Stanca Prezvitera, intre 1763 - 1765 de Constantin Potoceanul (capitan de jalbe) la curtea lui Constantin Nicolae Mavrocordat) si de sotia sa Maria, asa cum arata pisania bisericii, astazi disparuta: " Aceasta Sf(anta) biserica s-au fondatu la anulu 1765 septem(vrie) 15 cu toate cele necesare la infrumusetarea ei, de catre repausatulu intru fericire d(omnu)lu Constantin, ginerile d(umnea)lui Genea Potoceanu, impreuna cu sotia sa Maria. " In catagrafia din 1798 biserica este atestata ca lacasul de cult al mahalalei Apostol, care cuprindea 99 de case. Aici locuiau morarii, granarii, fainarii, brutarii, iar dupa infiintarea abatorului, s-au asezat si macelarii. De aceea lacasul s-a numit si "Biserica dela taiere". A servit si ca "Biserica de Judecata", tribunalul aflandu-se in spatele sau. De-a lungul timpului, biserica a suferit mai multe transformari si modificari. Reparatii radicale i-au fost facute in 1810, precum si intre 1820 si 1830 de Apostol Velicu "Bacanul"(ctitor nou si al bisericii "Staicu Bradu" - demolata). Un Apostol Marinciu "Brutarul" este inmormantat chiar in pronausul bisericii.
In anul 1864 a fost restaurata ca urmare a stricaciunilor cauzate mai ales de cutremurele din 1802 si 1838. Atunci s-a pus pardoseala din lespezi de piatra, iar invelitoarea facuta din sindrila, cu sageac s-a inlocuit in 1894, cu tabla de plumb. Concomitent, se renunta la stalpii si arcele care desparteau naosul de pronaos, largindu-se astfel spatiul interior.
Turla din zidarie de peste naos a fost inlocuita cu una mai usoara din lemn, imbracata cu tabla.
Turnul - clopotnita, ridicata ulterior, dupa alipirea pridvorasului actual, a fost mai intai din lemn apoi schimbata in anul 1910 din altul din metal.
Tot atunci s-a realizat un cafas pentru cor, la inceput din lemn, apoi din beton armat, in anii 1956-1957. Comisiunea monumentelor Istorice a elaborat inca din anul 1939, planul de restaurare, care nu s-a aplicat datorita izbucnirii razboiului. Aceste planuri prevedeau reconstituirea turlelor de peste pronaos si naos din zidarie a stalpilor si arcadelor din interior, ca si refacerea paramentului fatadelor.
Cutremurul din 1940, dar mai ales acela din 1977, au provocat mari stricaciuni ce au fost reparate abia in anul 1979.
Pictura initiala a bisericii a fost executata in tehnica fresco de Ioan erei Zugravu, iar in anul 1894 a fost refacuta in ulei de pictorii Gheorghe Tatarascu si I. Trombitescu. In anul 1924 este spalata si refacuta de catre Ioan Martinovici.
La restaurarile din acea perioada au contribuit baneste si Dumitru Mociornita, mare si generos industrias al vremii. Pictura a fost restaurata in anul 1983 de Virginia Videa, dar s-a inegrit , necesitand o noua spalare.
Pictura exterioara care consta in chipuri de sfinti in medalioanele situate deasupra ferestrelor a fost desfiintata pe trei dintre fatade, odata cu inaltarea zidurilor si largirea ferestrelor, la 1864. Icoana sfintei Paraschiva provine chiar din vremea zidirii, iar alte icoane din biserica sunt din anul 1864. Tampla din lemn a fost executata de C. M. Babic. Intre 1987 si 1989 in timpul regimului dictatorial Ceausescu, lacasul a fost amenintat intai cu daramarea, apoi s-a prevazut ridicarea unor blocuri de locuit pentru a-l ascunde vederii oamenilor. Numai prin demersurile adresate autoritatilor de partid si de stat, ca si ierarhilor Bisericii, dar si prin stradaniile proiectantilor si constructorilor, decizia a fost amanata mereu. Primejdia ridicarii blocurilor in fata bisericii a planat asupra acesteia pana in anii 1991 - 1992, cand, la neostoitele interventii ale preotului paroh Marian Sarbu (sprijinit de Arhiepiscopia Bucurestilor), a fost oprita executia constructiilor incepute in jur. Intre 1995 - 1996, fundatiile blocurilor au fost acoperite cu pamant.
In anul 2003 s-a refacut integral acoperisul bisericii, acoperindu-se cu tabla noua, jgheaburi si burlane de scurgere noi. Din anul 2004 s-au intocmit actele necesare pentru restaurarea picturii. Intre timp s-a refacut integral instalatia electrica pe conductori de cupru. Restaurarea picturii a fost executata de pictorul Marin Cotetiu, asistent la Facultatea de Teologie, sectia pictura. In anul 2007 s-a facut o solee solee (partea situata inaintea catapetesmei)noua din marmura de Ruschita si s-a pus parchet natural in Sfantul Altar. In anii 2008-2009 s-a pus pardoseala de marmura in toata biserica, s-a refacut instalatia de gaze si incalzirea centrala. De asemenea s-au confectionat strane noi sculptate in lemn de stejat natur. Intre sponsorii principali s-au numarat domnul Ion Antonescu (presendintele agentiei de turism Marshal) si domnul Ionescu Dan Nicolae. S-au refacut treptele de la intrarea in curtea bisericii cu placi de granit si porti metalice la intrare.
In faza de proiect este reamenajarea curtii parohiale, ridicarea unui asezamant social si a unei camere mortuare.