Ausgrabungen haben ergeben, dass die Geschichte der Stadtpfarrkirche von Tulln bis ins 11. Jahrhundert zurück reicht. Ein erster Bau hatte in etwa die Dimension des heutigen Mittelschiffes. Dieser wurde im Verlauf des 12. Jahrhundert auf die heutigen Ausmasse des dreischiffigen Gotteshauses erweitert. Im späten 13. Jahrhundert wurde das basilikale Langhaus von Grund auf im spätgotischen Stil neu gebaut. Der gotische Hochchor ist noch gut ein halbes Jahrhundert später entstanden. Nach einem Brand in der Zeit um 1500 wurde die bisherige Flachdecke des Langhauses mit einem Kreuzrippengewölbe ersetzt. Dem Tullner Stadtbrand von 1752 fiel fast die gesamte Innenausstattung zum Opfer. Aus diesem Anlass wurde die dem heiligen Stephan geweihte Kirche barock komplett neu eingerichtet. Gleichzeitig wurden die Doppeltürme erhöht und mit den heutigen Zwiebelhelmen bekrönt.
Baulich herrscht vor allem im Inneren der Pfeilerbasilika der gotische Stil vor. Der 1717 erbaute Hochaltar ist aus Marmor gefertigt und stammt aus dem von Kaiser Joseph II. aufgelassenen Karmeliterinnenkloster in St. Pölten. Er wurde 1786 nach Tulln gebracht. Das grosse Altarblatt zeigt die Steinigung des Kirchenpatrons. Es ist das Werk des Wiener Malers Joseph Steiner. Von ihm stammt auch das kleinere Trinitätsgemälde im Oberbereich des Hochaltars. Die Altarfiguren zeigen die Heiligen Leopold, Camillus, Rosalia und Magdalena. Ebenfalls aus einem aufgelassenen Kloster stammt das Chorgestühl. Es stand bis 1790 in der Kartause Gaming. Das Blatt „Maria Verkündigung“ im linken Seitenaltar ist die Kopie eines Gemäldes Franz Anton Maulbertschs, welches im Oberen Belvedere in Wien ausgestellt ist. Der rechte Seitenaltar weist ein Gemälde der hl. Luzia auf. Ein echtes Maulbertsch-Gemälde befindet sich am Altar der rechten Seitenkapelle. Die aufwendig verarbeitete spätbarocke Kanzel stammt vermutlich von Matthias Klöbl.
Im Kirchhof steht der Tullner Karner (Dreikönigskapelle). Er gilt als eines der herausragendsten erhaltenen Werke der Spätomanik in Österreich.