Området där Olaiparken ligger har troligen samlat norrköpingsbor i alla tider. På platsen ska stadsförsamlingens kyrka ha legat redan under mitten av 1300-talet – möjligen placerad söder om dagens och i trä – men än så länge är denna äldsta kyrkas byggnadshistoria okänd.
Den nuvarande kyrkan invigdes 1767 och var byggd direkt ovanpå den förras grunder. Eftersom stadsplanen och gatunätet hade lagts om efter branden 1655 kom den nya kyrkans orientering inte att sammanfalla med gatunätet utan är något skevt placerad, något som syns än idag. I samband med strukturförändringen passade man på att ta en del av den äldre kyrkogården i anspråk för att bli gatu- och tomtmark, t ex har man hittat tätt lagda gravar under de delar av Skolgatan som passerar dagens kyrkogård.
Strukturförändringarna påverkade också hur man gravlagde sina döda. En första fas med gravar, kanske i förhållande till den för oss ännu okända kyrkan, är placerade i rakt öst-västlig riktning. En senare fas med gravar som verkar härröra från efter mitten av 1600-talet och omstruktureringen, har i stället gravar orienterade i vsv-ono.
Olika gaturegleringar och stadsförändringar har genom åren påverkat kyrkotomtens storlek och utseende. När Olai Kyrkogatas sträckning tillkom någon gång under 1800-talets första hälft förlades den i nordsydlig riktning tvärs över kyrkogården och förbinder idag Knäppingborgsgatan med Skolgatan, och efter att S:t Olofsskolan stod klar år 1908 omvandlades med tiden det som varit den östra sidan av kyrkogården till skolgård och senare parkeringsplats.
Efter riksdagens beslut 1815 om att begravningar på kyrkogårdar inne i städerna skulle upphöra och nya begravningsplatser anläggas utanför stadsgränsen slutade man successivt att begrava på vid S:t Olai kyrka. Nu fick man i stället ta sig till stadsförsamlingens nya begravningsplats utanför staden, på Dragsgärdet, där Matteus begravningsplats invigts år 1811.