Stad, ontstaan bij een kruispunt van de belangrijke landwegen van het Rijnland naar Friesland en van Utrecht naar Duitsland. De vroegste vermelding, als ‘Audensele’, stamt uit 893.
Aan de waarschijnlijk al in de karolingische tijd gestichte kerk werd in 954 een kapittel verbonden. De nederzetting kreeg in 1049 van de Duitse keizer Hendrik III het recht een jaar- en weekmarkt te houden.
Wanneer Oldenzaal precies stadsrechten heeft gekregen, is onbekend, maar in 1222 blijkt het reeds versterkt te zijn. De stad was al in de 13de eeuw relatief belangrijk.
De immuniteit van de St. Plechelmus was tot in de 13de eeuw omgracht.
De stad werd waarschijnlijk in twee fasen uitgebreid tot de vrijwel ronde vorm die ze tot het eind van de 19de eeuw zou behouden en die in het beloop van de Noord-, OostWest- en Zuidwal nog herkenbaar is. In en om de stad lagen de hoven van de bisschop, het kapittel en de proosdij.In 1447 teisterde een brand de stad en voor een tweede keer in 1492, na inname door Gelderse troepen. Vanaf die tijd was de stad geregeld het slachtoffer van oorlogshandelingen. In de Tachtigjarige Oorlog gold ze als een van de belangrijkste vestingen van Oost-Nederland en verwisselde ze regelmatig van bezetter. De middeleeuwse verdedigingsgordel, bestaande uit muur, wal, binnen- en buitengracht werd uitgebreid met een gebastionneerd stelsel met negen bastions. Door de voortdurende oorlogshandelingen raakte de stad ontvolkt en nam haar functie als markt- en verzorgingscentrum voor de streek af. Gedurende het Twaalfjarig Bestand (1609-'21) was Oldenzaal in Spaanse handen en diende als de belangrijkste zetel van de katholieke autoriteiten boven de grote rivieren.
Deze politieke situatie had tot gevolg dat Noordoost-Twente sindsdien overwegend rooms-katholiek is gebleven. Na de inname van Oldenzaal door Staatse troepen in 1626 werden de vestingwerken geslecht; slechts een smalle gracht met drie poorten zou tot in de 19de eeuw de stad enige bescherming bieden.
Doordat in de 18de eeuw de weg van Deventer naar Hamburg enkele kilometers zuidelijk van de stad werd verlegd nam de verkeersfunctie van de stad af, maar door de aanleg van de zogenoemde Napoleonswegen in 1820-'30 werd de oude positie herwonnen. Vanaf 1840 nam de textielnijverheid in Oldenzaal snel in belang toe, zeker toen in 1865 door de aanleg van de spoorlijn Almelo-Salzbergen de stad werd aangesloten op het nationale en internationale spoorwegnet. De goedkope aanvoer van steenkool maakte de omschakeling van de huisweverij naar een fabrieksmatige productiewijze mogelijk. In de nabijheid van de spoorlijn werden textielfabrieken gevestigd, die tot 1876 nog op het grondgebied van de gemeente Losser lagen. De belangrijkste was de firma H.P. Gelderman & Zn.
Toch zou de stad een minder snelle ontwikkeling doormaken dan Almelo, Enschede en Hengelo. Voor de huisvesting van de textielarbeiders was binnen de stad al snel geen plaats meer; er kwamen arbeiderswoningen langs de uitvalswegen en er verrezen enkele kleine arbeiderswijken. Pas na de Tweede Wereldoorlog zou de stad een snelle ontwikkeling doormaken, zeker nadat in 1955 door een grenscorrectie de buurtschap Berghuizen bij Oldenzaal werd gevoegd. De stad ontwikkelde zich in recente tijd vooral in westelijke en noordelijke richting. Door nieuwbouw en stadssanering is toen ook veel van de oorspronkelijke stadsbebouwing verloren gegaan.
