W akcie lokacyjnym Olsztyna z 1353 r. znalazł się zapis, w którym wyłączono zakonników z prawa do nabywania, posiadania i przyjmowania darowizn w postaci wszelkiego rodzaju nieruchomości w tym mieście. Ten ogólny przepis, skierowany przede wszystkim przeciw Krzyżakom, spowodował zakaz osiedlania się wszelkich zakonów i mimo zniesienia go w 1772 r. był egzekwowany aż do początku XX w.
W 1918 r. śląska prowincja franciszkanów podjęła decyzję o otworzeniu swojej placówki w Olsztynie. Następnego roku pierwsza grupa zakonników przybyła do miasta i w dawnym kasynie oficerskim piechoty zorganizowano kaplicę pw. św. Franciszka z Asyżu. Franciszkanie byli więc pierwszym zakonem, który osiedlił się po ponad 600 latach przerwy.
W 1926 r., w 700. rocznicę śmierci św. Franciszka, rozpisano konkurs na budowę kościoła i klasztoru. Konkurs wygrał olsztyński architekt August Feddersen, który rok wcześniej okrył się chwałą po wybudowaniu gmachu teatru nad wyraz nowoczesnego i funkcjonalnego jak na ówczesne lata. Pierwszy projekt Feddersena nakreślał wizję kościoła utrzymaną w konwencji modernizmu, jednakże po wielu dyskusjach zakonnicy postanowili twardy warunek, aby styl budowli nawiązywał do włoskiego renesansu.
21 sierpnia 1926 r. biskup warmiński Augustyn Bludau poświęcił kamień węgielny, a już 2 października 1927 r. ten sam szafarz dokonał konsekracji świątyni. Kościół otrzymał główne wezwanie Chrystusa Króla i pomocnicze św. Franciszka z Asyżu. W 1930 r. prawie całe wyposażenie budowli było już gotowe i mimo że rok 1932 uważa się za datę zakończenia wszystkich prac, to dopiero w 1938 r. powstał ołtarz św. Franciszka. Ten zespół kościelno-klasztorny od samego początku był filią parafii św. Józefa, zaś w dawnej pierwszej kaplicy zakonnicy otworzyli Konwikt św. Antoniego przeznaczony dla uczącej się młodzieży męskiej.
Wybuch wojny przerwał ledwie zaczętą pracę franciszkanów, musieli oni opuścić pomieszczenia klasztorne, które zamieniono na tymczasowy lazaret wojskowy. Po wyzwoleniu Olsztyna klasztor przemianowano na szpital kolejowy, a następnie pediatryczny, zaś powracającym zakonnikom zwrócono tylko kościół i musieli oni zamieszkać w pobliskich kamienicach. Ten stan rzeczy trwał przez następne 30 lat. 2 lutego 1978 r. biskup Józef Drzazga erygował samodzielną parafię, która w 1991 r. została przekazana prowincji św. Franciszka z Asyżu w Poznaniu. Dawny budynek klasztorny, mocno zniszczony, zwrócono zakonnikom dopiero w 1993 r.; po dokonaniu najpotrzebniejszych napraw w 1998 r. franciszkanie powrócili do pierwotnego miejsca zamieszkania.