De basiliek staat op de plaats waar rond het jaar 765 missionaris Plechelmus het eerste kerkje stichtte, dat door hem aan de heilige Silvester werd gewijd. Plechelmus - in de achtste eeuw schreef men zijn naam als "Pleghelm" - maakte deel uit van de grote groep Angelsaksische missionarissen die in Echternach (Luxemburg) hun logistieke basis hadden en van daaruit de wijde omgeving introkken om de bewoners te kerstenen.
In 954 liet de Utrechtse bisschop Balderik van Kleef in Oldenzaal een nieuwe kerk bouwen en wijdde deze nu aan de man die het christendom in Oldenzaal gebracht had: Plechelmus. Diens relieken werden uit Sint Odiliënberg overgebracht naar zowel Utrecht als Oldenzaal. 
Het verheffen van die relieken vanuit het graf in een schrijn, tombe of altaar stond gelijk met de heiligverklaring van de persoon in kwestie. Plechelmus was vanaf dat moment Sint Plechelmus en tevens patroon van de nieuwgebouwde kerk in Oldenzaal.
Waarschijnlijk dateert het oudste romaanse gedeelte van de huidige kerk uit het begin van de 12de eeuw. De bouw van de basiliek was rond 1180 voltooid.
In 1447 woedde in Oldenzaal een hevige brand. Mogelijk is daarbij de romaanse zuidvleugel beschadigd geraakt. In ieder geval is op de plaats van deze romaanse zijbeuk tussen circa 1481 en 1500 een zijbeuk in gotische stijl opgetrokken. De nieuwe zijbeuk is ongeveer even hoog en breed als het middenschip. De traveeën van deze zijbeuk worden overwelfd door bakstenen stergewelven met geprofileerde zandstenen ribben.
De uitbreiding van het koor met een gotisch koortravee vond plaats in de jaren 1493 en 1494.
Rond 1525 (volgens anderen in het midden van de 15de eeuw) werd de noordelijke romaanse koorabsidiool afgebroken ten behoeve van de bouw van een gotische sacristie tegen de noordzijde van het koor.
