Podle kroniky Václava Hájka z Libočan sahá historie kostela v Liboci až do roku 992. Poté co na tomto místě pohanský Vršovec Hradovou, pán na Ruzyni, ze vzdoru proti knížeti zabil kněze Prostivoje, přikázal kníže Boleslav II. postavit nade vsí kamenný kostel ke cti Panny Marie a mučedníků Fabiána a Šebestiána. Tato zpráva není ovšem pokládána za věrohodnou.
Ves Liboc s přilehlým lesem Malejovem jsou zmiňovány při založení břevnovského kláštera roku 993, kdy je kníže klášteru daroval.
Farní kostel je v Liboci písemnými prameny spolehlivě doložen ve 14. století, archeologickými sondami již o století dříve. Po husitských válkách náležel straně podobojí, po rekatolizaci byl kostel péčí nejvyššího purkrabího Bernarda Ignáce z Martinic (+ 1685) „nákladně obnoven“. Samostatná farnost byla v Liboci obnovena roku 1702.
že kostel nevyhovoval co do velikosti, byl temný a navýšením terénu díky okolnímu hřbitovu i vlhký, byl nakonec roku 1842 zbořen a nahrazen novostavbou na tomtéž místě. Nový kostel byl pak 20. října 1844 benedikován zdejším farářem Františkem Lampou, který celou stavbu uskutečnil. Z té doby pochází také veliký obraz patronů kostela svatých Fabiána a Šebestiána od malíře Josefa Hellicha.
Mezi pozdějšími faráři vynikli svou horlivostí kněz – literát Vlastimil Hálek (1893 –1919) a vlastenec Václav Holub (1919 – 1950).
Poslední oprava kostela a zároveň úprava jeho interiéru podle liturgické reformy druhého vatikánského koncilu byly proveden v letech 1990 – 1991 péčí tehdejšího faráře Miroslava Vágnera. V roce 1996 svěřil pražský arcibiskup farnost a kostel do péče řádu karmelitánů.