Franciszkanie ze śląskiej prowincji Św. Jadwigi przybyli do Olsztyna wiosną 1919 r., zaraz po Świętach Wielkanocnych w liczbie 3 księży i 1 brata zakonnego. Było to wypełnienie postanowień kongresu prowincji na Górze Św. Anny w 1918 r., który podjął decyzję o zorganizowaniu w Olsztynie placówki.
Zakonnicy początkowo zorganizowali kaplicę p. w. Św. Franciszka z Asyżu w XIX-wiecznej kamienicy przy ul. Królewieckiej 9 (Aleja Wojska Polskiego), która dotąd mieściła kasyno oficerskie piechoty. W 700 rocznicę śmierci Św. Franciszka w 1926 r. rozpisany został konkurs na projekt kościoła i klasztoru franciszkańskiego. Konkurs wygrał August Feddersen architekt olsztyński, okryty chwałą po wybudowaniu w 1925 r., nowoczesnego i funkcjonalnego gmachu teatru. Pierwotna wizja świątyni nakreślona przez Feddersena była utrzymana w konwencji modernizmu, ojcowie jednak postawili warunek, aby kościół nawiązywał do renesansu włoskiego. Kościół usytuowany został przy Frauenstrasse (Stanisława Wyspiańskiego), na zamknięciu Hassenpflugstrasse (Józefa Kraszewskiego). Kamień węgielny pod kościół poświęcił 21 sierpnia 1926 r. biskup warmiński Augustyn Bludau, kościół otrzymał wezwanie główne Chrystusa Króla i dodatkowe Św. Franciszka z Asyżu. Święto Chrystusa Króla ustanowił papież Pius XI w 1925 r.
Kościół budowano w latach 1926-27, prace rozpoczęto 10 sierpnia 1926 r., wykonawcą robót była firma Karczewski z Olsztyna. Konsekracja odbyła się pod przewodnictwem biskupa Bludaua w dniu 2 października 1927 r. Wyposażenie kościoła w większości było gotowe w 1930 r., jedynie ołtarz Św. Franciszka jest późniejszy z 1938 r. Kościół był filią parafii Św. Józefa. Budowa klasztoru przeciągała się, ostatecznie prace ukończono w 1932 r. po zakończeniu budowy zespołu kościelno-klasztornego w dawnej siedzibie otwarto Konwikt Św. Antoniego, przeznaczony dla uczącej się młodzieży męskiej. W czasie II wojny światowej, w 1942 r., klasztor zamieniono tymczasowo na lazaret wojskowy. Większość zakonników opuściła Olsztyn w styczniu 1945, uciekając przed Armią Czerwoną, pozostali jedynie o. Gilbert Pawletta i br. Pankracy, którzy 3 stycznia 1946 r przekazali kościół polskim franciszkanom z prowincji Niepokalanego Poczęcia Najświętszej Marii Panny z Krakowa. Pierwszym polskim gwardianem był o. Sylwester Niewiadomy. W marcu 1945 r. klasztor przemianowano na szpital kolejowy, następnie pediatryczny.
Z uwagi na zajęcie klasztoru ojcowie zamieszkali obok kościoła w kamienicach przy ul. Klasztornej. Samodzielna parafia została erygowana przez biskupa Józefa Drzazgę w 2 lutego 1972 r., 19 marca 1991 r. parafia została przekazana prowincji Św. Franciszka z Asyżu z Poznania. W 1985 r. wybudowana została bursa, w miejscu dawnego zaplanowanego przez Feddersena skrzydła klasztornego. Mocno zniszczony budynek klasztoru zwrócono zakonnikom 6 kwietnia 1993 r., Dopiero w 1998 r., po dokonaniu najpotrzebniejszych napraw franciszkanie powrócili do pierwotnego miejsca zamieszkania.
