Der erste Entwurf für eine neue, durch steten Bevölkerungszuwachs notwendige Kirche im Brühler Osten stammt noch vom Altmeister des modernen Kirchenbaus, Dominikus Böhm aus Köln. Er hatte bereits 1951 einen Gesamtplan für den Gebäudekomplex mit Jugendheim, Kindergarten, Pfarr- und Küsterhaus und die Kirche entworfen. Sein Sohn Gottfried Böhm führte die Arbeit fort.
Der Schwerpunkt der Gemeinde war von Anfang an die Jugendarbeit, und so war auch das erste Bauwerk an dieser Stelle das Jugendheim, das fast 14 Jahre lang als Notkirche diente, bis die Kirche 1965 von Kardinal Frings geweiht werden konnte.
Ursprungsgedanke war, einen Kirchbau zu schaffen, der ohne Säulen von jedem Punkt der Kirche aus eine direkte Sicht auf den Altar erlaubt. Das war allerdings nur möglich, indem der große Raum durch eine Faltbetondecke überdacht wurde. So überragt die Kirche wie ein Zelt Gottes unter den Menschen den weiträumigen Gesamtkomplex.
Ungewöhnlich wie der Kirchenbau selbst ist auch der fast frei stehende schlanke Glockenturm.
Den suchenden Menschen anzusprechen war von Beginn an ein besonderes Anliegen in St. Stephan, und zwar sowohl von der äußeren Bauweise der Kirche her als auch durch die schlichte Klarheit der verwendeten gottesdienstlichen Geräte und Paramente. Die architektonische Gestaltung stand dabei in direktem Zusammenhang mit einer Form der Liturgie, die den mündigen Christen ernst nimmt und bereits vor ihrer Bestätigung durch das II.Vatikanische Konzil zum Volk hin zelebrierte Gottesdienste beinhaltete.
Bemerkenswert sind die hochgelegenen, farbigen Fenster nach einem Entwurf Gottfried Böhms. Sie zeigen Kristalle, die zeichenhaft den Aufbau der Kirche von Christus ausgehend darstellen. Das Altarkreuz des Kölner Bildhauers Hein Wimmer zeigt den am Holze erhöhten Christus als Hoherpriester. Auch die Leuchter und Altargeräte stammen von Wimmer. Schließlich ist noch die spätromanische Madonna hervorzuheben.
