Pod koniec XIX wieku Olsztyn bardzo szybko się rozwijał. Miasto należało wówczas do Cesarstwa Niemieckiego, a liczba mieszkańców stale rosła. Katolików było już ponad piętnaście tysięcy, jednak jedynym dużym kościołem nadal pozostawała średniowieczna katedra św. Jakuba. Dlatego w 1895 powołano komitet, którego celem była budowa drugiej dużej świątyni katolickiej.
Na nowy kościół wybrano teren położony wówczas niemal na obrzeżach miasta. Dziś trudno w to uwierzyć – wokół rozciągały się pola. Budowę finansowano głównie ze składek społecznych. Choć Olsztyn był w tamtym czasie miastem niemieckim, znaczna część mieszkańców mówiła po polsku. Istotną rolę w organizowaniu zbiórek odegrała także wydawana po polsku Gazeta Olsztyńska, która zachęcała mieszkańców do wspierania tej inicjatywy.
Mimo to podczas konsekracji świątyni dziewiętastego października tysiąc dziewięćset trzeciego roku burmistrz niemieckiego Allenstein Oskar Belian wygłosił przemówienie o wyraźnie antypolskim charakterze. Według zachowanych źródeł sprzeciwiał się również odprawianiu nabożeństw w języku polskim, co dobrze oddaje napięcia narodowościowe panujące w tamtym okresie.
Najbardziej charakterystycznym elementem kościoła jest strzelista wieża o wysokości około 83 metrów, która do dziś należy do najwyższych w mieście. Najcenniejszym elementem wyposażenia jest monumentalny neogotycki ołtarz główny, wykonany w 1911. Warto zwrócić uwagę również na oryginalne witraże oraz pozostałe elementy wystroju, które przetrwały II wojnę światową.
Podczas zdobywania Olsztyna przez Armię Czerwoną w 1945 znaczna część miasta została spalona lub zniszczona. Kościół Najświętszego Serca Pana Jezusa ocalał jednak niemal bez uszkodzeń. Dzięki temu do dziś można podziwiać oryginalne neogotyckie wyposażenie z początku XX wieku – ołtarze, ambonę, konfesjonały i piękne witraże.
W latach osiemdziesiątych XX wieku świątynia odegrała ważną rolę w życiu społecznym Olsztyna. Odbywały się tu msze za ojczyznę, spotkania środowisk związanych z NSZZ „Solidarność” oraz uroczystości patriotyczne. Do dziś we wnętrzu kościoła znajdują się liczne tablice upamiętniające działaczy opozycji, ofiary komunizmu i ważne wydarzenia z historii Polski.
