Um im Nürnberger Osten, einem sog. Missionsgebiet, das nur von einer Notkirche am Thumenberger Weg aus betreut wurde, ein kath. Gemeindezentrum errichten zu können, hatte die Gesamtkirchenverwaltung Nürnberg im März 1923 ein Grundstück in Mögeldorf erworben, das zwischen Lindnerstraße, Ostendstraße, Lechnerstraße und Thusneldastraße lag. Auf diesem sollten eine Kirche, ein Pfarrhaus und ein Schwesternhaus mit Kindergarten gebaut werden. Die Größe der Pfarrei wird in einem Schreiben von 1926 mit 3400 Seelen angegeben, "der größte Teil Industriearbeiter, die, religiös erkaltet, der Kirche fern stehen". Deshalb wurde vor allem auf die Räume für Kinder und Jugenderziehung Wert gelegt.
Weil Stadtpfarrer Johannes Roth den Kirchenbau direkt beobachten und überwachen wollte, wurde auf der Südostecke des Grundstückes 1925 als erstes das Pfarrhaus errichtet. Nachdem Pfarrer Roth ursprünglich den berühmten Clemens Holzmeister in Wien um einen Entwurf für St. Karl gebeten hatte, beschloss die Kirchenverwaltung 1926, einen bayerischen Architekten und anerkannten Kirchenbaumeister mit dem Projekt der neuen Kirche zu beauftragen. Dahinter stand wohl schon das Bestreben, Fritz Fuchsenberger aus München mit dem Auftrag zu betrauen. Sehr wahrscheinlich ging die Wahl Fuchsenbergers auf dessen Bereitschaft zurück, die Pläne kostenlos zu liefern. Prof. Ruff, Nürnberger Architekt und Mitglied des Baukunstausschusses, legte jedenfalls wegen dieses standeswidrigen Verhaltens beim Baukunstrat der Stadt Nürnberg und beim Bund Deutscher Architekten Beschwerde ein. Während des ganzen Bauvorgangs bleibt jedenfalls Fuchsenbergers Umgang mit den finanziellen Mitteln undurchsichtig und hatte einen umfangreichen Briefwechsel zur Folge. Von der ursprünglichen Idee, einen Wettbewerb zu veranstalten, sah man offenbar ab.
Für den Altar und alle damit in Zusammenhang stehenden Metallarbeiten fertigte Fritz Fuchsenberger selbst die Entwürfe; die Werkstätte des Münchner Silberschmiedes Alois Wöhrle führte sie in den Jahren 1927/28 aus. Auch Gestühl, Beichtstühle, Windfang, die Wandleuchter und die Pflasterung des Fußbodens wurden nach Entwürfen Fuchsenbergers angefertigt.
Die Ausstattung des Altarraums mit dem reichen Retabel und allem dazugehörigen Gerät war nur möglich durch eine großzügige Spende des Nürnberger Industriellen Robert Pfaller. Auch für die Farbfenster nach Entwürfen Thalheimers, mit denen sowohl die Unterkirche als auch der Chorraum geschmückt wurden, kam diese Stiftung auf.
Die Seitenaltäre blieben zuerst ohne Schmuck. In den Jahren 1939/40 konnten dann aus der Abtei St. Walburg in Eichstätt Teppiche erworben werden, die zum Teil neu gewebt waren, zum Teil in einer Zweitverwendung nach St. Karl kamen und mit denen die Ausstattung im wesentlichen komplettiert war.
Der Krieg hat dank der Wachsamkeit des Messners Karl Jäckle in St. Karl keine größeren Schäden angerichtet. Die Chorverglasung wurde zerstört, und der Wandbehang hinter dem Altar verbrannte. Diese Verglasung wurde 1968 durch Fenster des Kunstmalers Alfons Abels ersetzt. Als jüngste Ausschmückung der Kirche wurde 1978/79 ein Mosaik in die Nische der Westwand eingefügt. Es zeigt den Patron der Kirche, St. Karl Borromäus, nach einem Entwurf des Malers Anton Greiner aus Stegaurach.