Ausgrabungen zeigen, dass die Geschichte der Tullner Stadtpfarrkirche bis ins 11. Jahrhundert zurückreicht. Der erste Bau entsprach in etwa der Grösse des heutigen Mittelschiffs. Im 12. Jahrhundert wurde er zu einer dreischiffigen Kirche erweitert. Im späten 13. Jahrhundert entstand das basilikale Langhaus in spätgotischer Form; der gotische Hochchor folgte gut ein halbes Jahrhundert später. Nach einem Brand um 1500 ersetzte man die bis dahin vorhandene Flachdecke des Langhauses durch ein Kreuzrippengewölbe. Beim grossen Stadtbrand von Tulln im Jahr 1752 wurde fast die gesamte Innenausstattung zerstört. Die dem heiligen Stephan geweihte Kirche erhielt daraufhin eine vollständige barocke Neueinrichtung. Gleichzeitig erhöhte man die Doppeltürme und setzte ihnen die heutigen Zwiebelhelme auf.
Im Inneren der Pfeilerbasilika dominiert trotz der späteren Eingriffe weiterhin die Gotik. Der 1717 errichtete Hochaltar aus Marmor stammt aus dem Karmeliterinnenkloster in St. Pölten, das Kaiser Joseph II. auflösen liess; 1786 wurde er nach Tulln überführt. Das grosse Altarbild, geschaffen vom Wiener Maler Joseph Steiner, zeigt die Steinigung des Kirchenpatrons. Von Steiner stammt auch das kleinere Trinitätsgemälde im Oberteil des Altars. Die Figuren am Altar stellen die Heiligen Leopold, Camillus, Rosalia und Magdalena dar.
Das Chorgestühl, ebenfalls aus einem aufgelassenen Kloster, kam 1790 aus der Kartause Gaming hierher. Das Gemälde „Maria Verkündigung“ im linken Seitenaltar ist eine Kopie nach Franz Anton Maulbertsch, dessen Original im Oberen Belvedere hängt. Der rechte Seitenaltar zeigt die heilige Luzia, während sich ein echtes Werk Maulbertschs am Altar der rechten Seitenkapelle befindet. Die reich gearbeitete spätbarocke Kanzel wird Matthias Klöbl zugeschrieben.
Im Kirchhof steht der Tullner Karner (Dreikönigskapelle), eines der bedeutendsten erhaltenen Bauwerke der Spätromanik in Österreich.