De Sint Plechelmusbasiliek is rond 1150 als een driebeukige kruisbasiliek gebouwd van Bentheimer zandsteen, in romaanse stijl, en is daarmee een van de eerste voorbeelden in Nederland van zandsteenarchitectuur. De bouw vond plaats in de directe nabijheid van een oudere kerk, een stenen zaalkerk van 27 bij 12 meter, gesticht door Bisschop Balderik (918-976).
De toren werd omstreeks 1240 aan de kerk toegevoegd. Vervolgens is rond 1480 de romaanse zuidbeuk belangrijk vergroot en kreeg deze een gotisch uiterlijk. Na 1500 werd het priesterkoor in gotische stijl verlengd. De huidige Sacristie aan de noordzijde is in 1930 gebouwd, zo'n 30 jaar nadat de basiliek onder leiding van Joseph Cuypers was gerestaureerd. Ondanks deze restauratie en ondanks een grote brand in 1492 is 85% van het oorspronkelijke gebouw in tact gebleven.
In 1950 kreeg de kerk de eretitel 'Basiliek', om uiting te geven aan de grote betekenis van de kerk voor de rooms-katholieke gemeenschap van Oldenzaal en de wijde omgeving.

Plechelmus was een monnik van Angelsaksische (Ierse) afkomst, die omstreeks 765 het katholieke geloof verkondigde in een gebied aan weerszijden van de huidige Duits-Nederlandse grens, min of meer samenvallend met de latere bisdommen Utrecht en Münster. Over het leven van Plechelmus is weinig bekend - zijn Vita staat op de website van de Plechelmusbasiliek - maar wel dat hij in een ontmoeting had met koning Pepijn III, ergens tussen 751 en 768. Zijn uitvalsbasis zou het klooster St. Odiliënberg zijn geweest, in de buurt van Roermond.

bron: 'Plechelmus, zijn kerk, liturgie en kapittel', redactie Guus Goorhuis en Jan Oude Nijhuis, Walburg Pers 2005.