Im Jahre 1168 wird Tulln zur Pfarre erhoben. Gleichzeitig dürfte der Bau der dreischiffigen romanischen Pfeilerbasilika zum hl. Stephan mit den markanten beiden Westtürmen begonnen haben. Noch heute befinden sich romanische Bauelemente an der von 1486 bis 1513 gotisierten und eingewölbten Kirche. Besonders bemerkenswert ist das romanische Westportal, das wohl zu Beginn des 13. Jahrhunderts entstanden sein dürfte und aus einem, auf mäßig steilen romanischen Basen ruhenden, Rundwulst gebildet wird. Einzigartig sind die rechts und links davon angebrachten Reliefs von je sechs Halbfiguren in Rundbogennischen. Über dem Westportal schwebt ein gekrönter Adler mit einem Türkenschädel in seinen Fängen. Aus der ersten Hälfte des 14. Jahrhunderts stammt der gotische Langchor mit seinen hohen Maßwerkfenstern, Strebepfeilern und Kreuzrippengewölben mit Birnstab nach Art der Bettelordenskirchen.