De buurschappen van Olst maakten aanvankelijk deel uit van de uitgestrekte parochie Luchere, die waarschijnlijk was gelegen in het schaars bevolkte gebied tussen de parochies van Deventer, Raalte en Zwolle. In de loop van de 13de eeuw ontstond een zelfstandige parochie Olst, waarvan de oprichting mogelijk omstreeks 1234 werd voorbereid, toen bisschop Otto I op zijn hof in Olst verbleef; misschien vond zelfs bij die gelegenheid al de inwijding plaats van de nieuwe parochiekerk, de Willibrordkerk.
Van hofkapel naar parochiekerk
De Willibrordkerk, tegenwoordig meestal dorpskerk genoemd, is verrezen op het hoogste punt van een rivierduin midden in het kerngebied van de vroegere hof Holsto, eigendom van het vrouwenklooster van Essen. De dorpskerk werd vroeger aan alle zijden omgeven door bezittingen van het Essense klooster. We nemen daarom aan dat de resten van een vermoedelijk 12de-eeuws, tufstenen fundament, dat bij een kerkrestauratie onder de dorpskerk is gevonden, afkomstig moet zijn van een kapel van het klooster die op die plek heeft gestaan. Waarschijnlijk was die kapel oorspronkelijk van hout gemaakt en werd ze in de 12de eeuw vervangen door een tufstenen bouwwerk. De kapel was ongeveer zestien meter lang en acht meter breed. Het aan de westzijde gelegen portaal was vier bij vier meter. De overblijfselen van de kapel liggen binnen de muren van het schip van de huidige dorpskerk. De buitenmuren van de nieuwe kerk zijn dus om de overblijfselen van haar voorganger heen gebouwd.
St. Willibrord
De parochiekerk van Olst werd opgedragen aan St. Willibrord, de bekende missionaris en bisschop van Utrecht, die volgens de overlevering zelf opdracht voor de bouw van de kerk heeft gegeven. Erg waarschijnlijk is dat niet, omdat Willibrord al in het jaar 739 is gestorven. In die tijd was het IJsseldal nog grotendeels in handen van heidense Saksen. Pas na de verovering van dit gebied door Karel de Grote, aan het einde van de 8ste en het begin van de 9de eeuw, komt de kerstening goed op gang. Daar komt nog bij dat de eerste schriftelijke vermelding van Willibrord als beschermheilige van de kerk pas uit 1572 dateert. Het kapittel van St. Lebuïnus in Deventer bezat het benoemingsrecht van de pastoor.
Middeleeuwse verbouwingen
De Willibrord is in de loop van de eeuwen ingrijpend veranderd en heeft daardoor in- en uitwendig een heel ander uiterlijk gekregen. Voorzover valt na te gaan vond de eerste belangrijke verbouwing van de vroegere hofkapel omstreeks 1336 plaats. De deken van het kapittel van Deventer schonk toen twee ponden aan de kerk "voor het bouwen". Uit dit legaat is waarschijnlijk de bouw van het koor betaald. Een tweede ingrijpende verbouwing of misschien wel volledige nieuwbouw werd in de jaren 1493-1494 uitgevoerd en had betrekking op het kerkschip, dat werd verbreed en verhoogd. Men heeft bij die gelegenheid ook de toren op zijn huidige hoogte gebracht, en het ligt voor de hand dat toen eveneens het koor is aangepast aan de nieuwe vorm van het schip.
Verwarring over namen en jaartallen
In de kerk zijn namen en jaartallen aangebracht, die lijken te verwijzen naar de ontstaansperiode van de parochie. Er is helaas verwarring ontstaan over de juistheid van deze opschriften. Volgens J.H. Hofman was in het midden van de 19de eeuw in een steen boven de triomfboog het jaartal 1275 uitgehouwen. Bij een latere verbouwing in diezelfde eeuw heeft men deze steen vermoedelijk verwijderd en in plaats daarvan de tekst "Thomas Loeningen 1267" aangebracht. Nog weer later is om onduidelijke redenen dit opschrift weer vervangen door de tekst "Thomas Loemken anno 1264". Kennelijk zijn er fouten gemaakt bij het ontcijferen van de opschriften. We weten helaas niet wie Thomas Loeningen en Thomas Loemken zijn. Opmerkelijk is wel dat de jaartallen 1264, 1267 en 1275 verwijzen naar de periode waarin de parochie moet zijn gesticht of de kerk in gebruik werd genomen.