Van de buitenkant oogt het massieve zandstenen bouwwerk haast wat lomp, maar aan de binnenzijde is de Plechelmusbasiliek een toonbeeld van rust en harmonie. Kleine rondboogvensters, imposante pijlers en sierlijke gewelven zijn typerend voor de romaanse bouwstijl. De Oldenzaalse kruisbasiliek is een van de oudste kerken in Overijssel. De bouw van de overwelfde kerk is begonnen voor 1150 en werd een eeuw later voltooid met een robuuste toren. Terwijl de nog oudere romaanse Lebuinuskerk in Deventer rond 1500 tot hallenkerk in gotische stijl met kenmerkende spitsboogvensters verbouwd werd, bleef in de Plechelmusbasiliek - ondanks enkele soortgelijke aanpassingen aan met name het koor - de oude romaanse sfeer behouden.
Kapittelkerk
De Plechelmusbasiliek getuigt van de bijzondere rol van Oldenzaal in de provinciale kerkgeschiedenis. In 954 had bisschop Balderik een kapittel in Oldenzaal gesticht. Dit college moest hem bijstaan in geestelijke en bestuurlijke taken in Twente. Het Oldenzaalse kapittel kreeg de beschikking over een nieuw stenen kerkgebouw, waaraan de naam van de heilige Plechelmus werd gekoppeld, die het voortouw had genomen bij de kerstening van deze streek. Zijn relieken werden naar Oldenzaal overgebracht. Ook Deventer beschikte over een eigen kapittel en in 1291 kwam er in Steenwijk een derde kapittel. Vanuit deze religieuze centra werden nieuwe kerken in de omgeving gesticht. Uiteindelijk kwamen in Overijssel 52 kerkelijke verzorgingsgebieden, parochies of kerspels genaamd, tot stand. In de 12de eeuw ontwikkelden het Oldenzaalse en Deventer kapittel zich tot overkoepelende aartsdiaconaten, bestuurlijke eenheden, binnen het bisdom Utrecht. Zo kon Oldenzaal uitgroeien tot kerkelijke hoofdstad van Twente. Ook na de Reformatie zou de stad de functie van katholiek steunpunt blijven vervullen.
Kerkenbouw
De centrale rol die het christelijk geloof in de middeleeuwse samenleving speelde, blijkt tot op heden uit de monumentale bouwwerken die in de toenmalige nederzettingen verrezen: van het kleine romaanse kerkje bij Wilsum uit ca. 1050 en vele andere eenbeukige dorpskerken tot de grote hallenkerken in de welvarende steden. De bedehuizen waren niet alleen uiting van religieuze toewijding, maar golden evengoed als teken van lokale voorspoed. Menig kerk of toren werd zo ambitieus ontworpen, dat deze nooit of slechts gedeeltelijk werd afgebouwd. Bijzonder aan de middeleeuwse kerkenbouw in Overijssel is het veelvuldig gebruik van tufsteen en Bentheimer zandsteen. Deze werden per schip of paard en wagen uit het Duitse grensgebied aangevoerd. Soms gebruikte men lokaal gewonnen ijzeroer. Ook in architectonisch opzicht zijn veel Duitse invloeden zichtbaar. Zo kreeg in de Kamper Bovenkerk de gotische bouwkunst tijdens de 14de eeuw luisterrijk vorm. De beroemde bouwmeester Rutger van Keulen ontleende hierbij inspiratie aan de dom van Keulen en de kathedraal van Praag. In dergelijke majestueuze kerkgebouwen echoot de diep religieuze, onverdeelde samenleving van de Middeleeuwen nog na.
