1267 wird erstmals eine „Ecclesia in Tobelice“ urkundlich erwähnt. („Tobelice“, der älteste Name des heutigen „Döbling“, bedeutet – nach einer germanischen Namenserklärung – eine Schlucht , in der ein Bach „tobt“, was ja, auf den Krottenbach bezogen, verständlich ist. Nach einer slawischen Namenserklärung heißt „Tobel“ soviel wie „heiße Quelle“, was vielleicht auch in unserem Fall passen könnte, vgl. „Tobelbad“ in der Steiermark oder „Teplice“ in Böhmen. Im nahen Heiligenstadt befanden sich ja bis ins 19. Jahrhundert warme Quellen, die den Ort zu einem Kurort machten. Über diese erste Döblinger Kirche ist nur wenig überliefert. Einige Abbildungen geben uns über ihr Aussehen Auskunft.
Als Kaiser Friedrich III. 1469 erreicht, dass Wien eine eigene Diözese wird, die von der bisherigen riesigen Diözese Passau abgetrennt wurde, werden 3 Stadtpfarren und 14 Landpfarren genannt, darunter auch Döbling.
Bedingt durch die Auswirkungen der Reformation, den großen Priestermangel und die allgemeine Armut nach der 1. Wiener Türkenbelagerung und die Verhältnisse im Dreißigjährigen Krieg entschließt sich 1640 das „bischöfliche Konsistorium“ zur Auflassung der Pfarre Döbling. Mehr als 140 Jahre wird dadurch Döbling durch den Pfarrer von Währing betreut.
Als die Türken 1683 Wien abermals belagern und Wiens Umgebung völlig verwüstet wird, wird auch Döblings St. Paulskirche zerstört.
Die Regierungszeit Kaiser Karls VI. und seiner Tochter Maria Theresia im 18. Jahrhundert bringen friedliche Entwicklung und wirtschaftlichen und kulturellen Aufschwung im Zeitalter des Barocks. Wohlhabende Wiener lassen sich für die Sommermonate elegante Landhäuser in Döbling errichten, und einer von ihnen, Wolff Joseph Hoffmändl von Mangeram, lässt an der Ecke der Döblinger Hauptstraße/ Hofzeile ein privates Kirchlein, zum hl. Johann Nepomuk, erbauen, in dem von ihm bezahlte Priester aus Währing oder Lichtenthal Gottesdienste feiern.
Im späten 18. Jahrhundert, zur Zeit Kaiser Josefs II., im Zeitalter der Aufklärung, finden große kirchliche Veränderungen in Österreich statt. Auf Drängen vieler neu angesiedelter Döblinger und besonders der Äbtissin der Tullner Dominikanerinnen, die zu jener Zeit die Döblinger Grundherrschaft innehaben, entschließen sich Kaiser und Erzbischof im Jahre 1783 die Pfarre Döbling wieder zu errichten. Das bisher zur Pfarre Heiligenstadt gehörende Unterdöbling wird der neueingerichteten Döblinger Pfarre angeschlossen, und der bisherige „Benefiziat“ (bezahlter Messeleser) aus Währing, Sebastian Fux, wird zum ersten Pfarrer ernannt. - Nun ergibt sich die Frage, ob die kleine, baufällige St. Paulskirche Pfarrkirche werden soll oder lieber die zwar auch kleine, aber schönere St. Johann Nepomuk Kapelle. Angeblich soll Kaiser Josef II. persönlich in Döbling gewesen sein und sich für St. Paul entschieden haben, unter der Voraussetzung, dass diese Kirche neu zu errichten sei. 1785 wird das St. Nepomuk Kirchlein geschlossen und die Einrichtung versteigert. Ein Tischler erwirbt das Gebäude und macht daraus ein Holzmagazin.
1794 steht noch immer keine neue St. Paulskirche. Auf Grund der Bitten der Döblinger wird nun das St. Nepomukkirchlein wiederum geweiht und eingerichtet und soll bis zur Errichtung einer neuen St. Paulskirche als provisorische Pfarrkirche dienen.