Świątynia wybudowana w latach 1894-1896 na fundamentach starego kościoła gotyckiego (ok. XIII w.), lecz później wielokrotnie przebudowywanego. Pierwotnie nosił on wezwanie św. Gertrudy.

Budowa kościoła zakończyła się 17 grudnia 1896 r. Oto jak na ten temat pisała gazeta „Neue Stettiner Zeitung”:

Dziś rano miało miejsce poświęcenie nowo wybudowanego kościoła św. Gertrudy. Na tę uroczystość zebrali się członkowie Rady Kościelnej, przedstawicielstwo Gminy, przedstawiciel Królewskiego Konsystorza, rząd i zgromadzenie zarządu magistratu i miasta oraz liczni duchowni z miasta i prowincji i wielu dostojnych honorowych gości zebranych w fundacji Gertrudy. Prezes Konsystorza dr Richter wygłosił przemówienie, w którym wspomniał na jakie trudności napotykała budowa ukończonego obecnie kościoła św. Gertrudy i doprowadzenie jej do obecnego stanu, oraz podkreślił, że jest to do zawdzięczenia panu pastorowi Müllerowi, że to dzieło zostało doprowadzone do stanu takiego, jaki sobie życzono. Konsystorium wyraża za to panu pastorowi Müllerowi podziękowanie i cieszy się, że na wniosek władz, jako uznanie dla jego zasług, może mu przekazać Czerwony Order Orła. Pan pastor podziękował za uznanie i przyrzekł trwać dalej w wiernym spełnianiu obowiązków. Po tym obecni udali się do kościoła. Na czele pochodu kroczyli członkowie Rady Kościelnej i przedstawicielstwo parafii, niosąc święte przedmioty, do nich dołączyli również inni panowie. Przy pojawieniu się okazałego pochodu rozbrzmiewały uroczyście, po raz pierwszy, dzwony kościelne, które to swego czasu zamilkły na szereg długich lat. Ponieważ, jak wiadomo, stary kościół św. Gertrudy został zimą 1888/89 zburzony, a już w roku 1887 na polecenie budowlanej inspekcji policyjnej zamknięty, odprawiano nabożeństwa dla parafii św. Gertrudy w kościele św. Jana.

Przed głównym portalem pochód zatrzymał się. Kierownik budowy pan Bold wystąpił naprzód i przekazał klucze nowego kościoła architektowi miasta Meyerowi, a ten wraz z przemówieniem wręczył je panu generalnemu superintendentowi dr Pötterowi, od którego ten klucz przyjął pastor Müller i otworzył drzwi kościelne, po czym goście udali się do jasno oświetlonego kościoła, który wkrótce zapełnił się biorącymi udział w nabożeństwie. Uroczystość kościelna rozpoczęła się śpiewem chóru „Machet die Tore auf” („Otwórzcie się szeroko podwoje świątyń bram”) po czym zbór zaintonował „Wie soll ich dich empfangen” („Jak mam powitać Ciebie”). Kiedy przebrzmiały ostatnie strofy, wystąpił przed ołtarz, który młode dziewczęta odświętnie przybrały kwiatami, pan generalny superintendent dr Pötter, który swoim donośnym głosem wygłosił mowę z okazji poświęcenia kościoła, którą zakończył modlitwą. Teraz rozbrzmiały nowe organy po raz pierwszy ze śpiewem parafian: „Nun danket alle Gott” („Dziękujmy Bogu wraz”). Kiedy chór przestał śpiewać, pan kaznodzieja Silex rozpoczął liturgię przy czym obecni śpiewali razem zdanie przeznaczone dla zboru. Następnie pan pastor Müller wygłosił pierwsze kazanie w nowym kościele. Potem odmówił modlitwę i udzielił błogosławieństwa. Wraz z ostatnim wierszem śpiewanej pieśni uroczystość znalazła swoje zakończenie.

Kościół został uszkodzony podczas II wojny światowej, opustoszały kilka razy zmieniał właścicieli. Do parafii luterańskiej powrócił w 1959 roku. Po remoncie, 16 października 1960 kościół otrzymał nowe wezwanie – Świętej Trójcy.

Organy firmy „Schlag und Söhne” z 1917 roku znajdujące się w kościele pochodzą z opuszczonego kościoła w Wałbrzychu-Sobięcinie, a neoromańska chrzcielnica została przyniesiona z kaplicy przy ul. Wawrzyniaka w Szczecinie.