Durch das rasche Wachstum der Stadt Tuttlingen erhöhte sich die Zahl der Katholiken in den Nachkriegsjahren erheblich. Die Stadt hatte Mitte der 1950er Jahre ca. 7 000 katholische Einwohner. Diese große Zahl der Gläubigen und die flächenmäßige Ausdehnung der Stadt machten den Bau einer weiteren katholischen Kirche unumgänglich. Zunächst entstand eine zweite Kirche in der Mühlau.

Das Lager Mühlau, für osteuropäische Zwangsarbeiter im Krieg errichtet, hatten die Franzosen in ein großes Lager für deutsche Kriegsgefangene umgewandelt und für diese eine Lagerkirche erstellt. Nach Auflösung des Lagers erhielt die katholische Kirchengemeinde diese Kirche als Geschenk; lediglich der Platz musste gekauft werden. Von 1952 bis 1964 gab es in der Mühlau eine Holzkirche mit dem Namen „Kirche zur Auferstehung unseres Herrn Jesu Christi und zu Ehren des Heiligen Bruder Nikolaus von der Flüe“. Diese provisorische Kirche musste dem Neubau des Schulzentrums weichen.
Nach komplizierten Kauf- und Tauschaktionen war der Bauplatz für einen Kirchenneubau an der Ecke Kreuz-, Berg- und Freiburgstraße im Westteil der Stadt gefunden. 1957 wurde ein Kirchenbauverein gegründet, 1958 ein Wettbewerb ausgeschrieben. Der Plan der Architekten Franz J. Gottschlich und Max W. Schraube, Tuttlingen, wurde favorisiert und verwirklicht.

Bereits zu Beginn der Planung wurden Architektur und künstlerische Gestalt aufeinander abgestimmt, um ein stimmiges Konzept und eine durchgeformte Einheit für den Kirchenbau zu finden.

Herausragende, zeitgenössische Künstler wirkten am Bau mit: Franz Bucher, Wilhelm Geyer, Emil Kiess.

Am 4. März 1961 war der erste Spatenstich und Erzabt Dr. Benedikt Reetz aus Beuron segnete am 25. September 1961 den Grundstein. Bischof Carl-Josef Leiprecht weihte die Kirche am 18. Mai 1963. Kindergarten und Schwesternwohnung waren bereits im September 1962 eingeweiht worden.
Die kubischen Baukörper der Kirche zeigen wenig Gliederung. Der machtvolle Glockenturm, in der italienischen Campaniletradition, von der Kirche getrennt, setzt einen Akzent im Stadtbild.

Äußerlich einem Block ähnelnd, erahnt man kaum die Wirkung des Kircheninnenraums. Zu beiden Seiten des Eingangs stehen zwei Lichtwände in Betonfachwerkart ausgeführt. Ebenfalls vorne, dem Altar zu sind sie ohne Unterbrechung und um die Ecke bis zum Sakristeianbau fortgeführt.

Der ganze Baublock sitzt mit dem Eingang auf dem Boden auf und wird am unteren Teil des Hanges vom Sakristeibau gestützt. Unter den mächtigen Tragbalken befinden sich die Fenster des Gemeindesaals. Die hellen Metallflügel der beiden Eingangstüren der Kirche sind das Werk von Franz Bucher. Das Kircheninnere ist als weite Halle gestaltet. Vier Betonpfeiler tragen zwei wuchtige Betonbalken, die nach vorne und nach hinten überkragen und sich dabei verjüngen. Auf ihnen liegen Querbalken, auf denen das Dach ruht. Man wird an einen Baldachin erinnert, der von Glas und Beton umhüllt ist
Dach und Seitenwand werden streng durch eine kleine Lichtfuge getrennt. In die Felder der Lichtwände komponierte Emil Kiess in Glasbeton einen harmonischen Farbkanon, der an die Buntglasfenster französischer Kathedralen erinnert. Die beiden rückwärtigen Wände gestaltete er farblich ganz verhalten, um einerseits damit die Hauptrichtung zum Altar hervorzuheben, andererseits aber den Glasbildern zur Wirkung zu verhelfen. Hinten, neben der Orgelempore, entstanden die Taufkapelle und die Seitenkapelle mit Kreuzweg. Die Glasmalereien sind von Wilhelm Geyer und stellen in der Taufkapelle die Taufe Jesu, das Gespräch Jesu mit der Samariterin am Jakobsbrunnen, die Begegnung Jesu mit Nikodemus und in der Seitenkapelle den Kreuzweg dar. Altäre, Taufbecken, Altarkreuz, Ambo und Wandbilder, die mit Hammer und Meißel aus den Betonplatten herausgearbeitet sind schuf Franz Bucher.

Die Bilder der Altarwand zeigen Szenen aus dem Leben Mariens. Im Uhrzeigersinn sind dies von oben rechts: Die Ausgießung des Heiligen Geistes an Pfingsten, die Verwandlung des Wassers in Wein auf der Hochzeit zu Kana, die Kreuzigung des Herrn, die apokalyptische Frau (Vision des hl. Johannes) und in der Mitte als Titelbild der Kirche, die Krönung Mariens durch die Allerheiligste Dreifaltigkeit.

Der übergeordnete Gedanke der Bilder an den Seitenwänden ist die Erlösung des Menschen. Die theologische Thematik stammt vom früheren Stadtpfarrer und Dekan Alfred Barth und ist unter einem doppelten Gesichtspunkt ausgeführt. Zum einen ist durch das Wirken Gottes die Erlösung des Menschen sein freies Geschenk aus Gnade. Zum anderen kann der Mensch durch sein Tun an der Erlösung mitwirken. In der ganzen Heilsgeschichte wirkt beides zusammen. In einzelnen Ereignissen tritt jedoch das Engagement Gottes oder die Mitwirkung des Menschen deutlicher hervor.

Die linke Wand (Blickrichtung zum Altar) zeigt in 11 Feldern das Handeln Gottes und bietet eine Auswahl biblischer Szenen, in denen Gottes Allmacht sowie menschliche Schuld und Ohnmacht deutlich werden: Gott erschafft den Menschen, Gott verheißt die Erlösung, Gott rettet den Noach, das Opfer Abrahams, Jakobs Traum, der brennende Dornbusch, die eherne Schlange, die Propheten Elia und Elischa, die Vision des Propheten Ezechiel von der Auferweckung Israels , Gottes Sohn wird Mensch, der wunderbare Fischfang, die wunderbare Brotvermehrung, die Verklärung auf dem Berg.

Die Bilder der rechten Wand handeln von der Mitwirkung des Menschen; seine Erlösung ist der Lohn für sein eigenes Mittun: Gott erschafft den Menschen, der Turmbau zu Babel, Jakob kämpft mit dem Engel, Auszug aus Ägypten, die Zehn Gebote und das Goldene Kalb, Elias auf dem Karmel, David und Goliath, Esther und Judith, Zacharias und Maria, Darstellung des Herrn, der Jesusknabe im Tempel, die Zehn Jungfrauen, die Salbung Jesu in Betanien, die Auferweckung des Lazarus, der Glaube des Thomas.

Darüber hinaus ist die Kirche mit folgenden Skulpturen ausgeschmückt: links vom Altar eine Muttergottes mit Kind aus dem Ende des 15. Jahrhunderts, an der linken Schiffswand hinten eine Pieta aus dem Anfang des 18.Jahrhunderts und hinten am rechten Pfeiler ein Hl. Joseph mit Kind, ebenfalls aus dem Anfang des 18.Jahrhunderts.

Die 34 Register umfassende Orgel aus dem Jahre 1989 ist ein Werk der Orgelbaufirma Jehmlich, Dresden.

Link: „Chronik“ 50 Jahre Maria Königin