Legenda spune că prin 1092, regele Ungariei (Ladislau I) se afla la vânătoare prin Țara Crișurilor și, lăsându-se noaptea, a hotărât să facă tabăra aici, pe Crișul Repede. Odată căzut într-un somn adânc, în vis i-a apărut Fecioara Maria, care i-a spus să ridice o biserică în acel loc.
Îndrăgostit fiind de loc, a lăsat vorbă ca, la moartea sa, rămășițele sale pământești să fie aduse în biserica ridicată de el în onoarea Fecioarei Maria. Datorită devotamentului său față de creștinism și, în special, catolicism, Ladislau, numit și cel Sfânt, a atras mii de pelerini la locul de veci, ceea ce a motivat regalitatea maghiară să fortifice biserica, ducând, prin urmare, la dezvoltarea regiunii din jur.
În 1241 invazia tătarilor ajunge în zona Crișurilor, devastând totul în urma lor. La data resprectivă, cetatea Oradiei se prezenta sub o altă formă, fiind protejata de un val de pământ și palisade, ziduri de piatră și turnuri în anumite locuri. Primul val de tărari care au ajuns aici erau călăreți arcași, care nu au reușit să producă pagube importante masivei cetăți și prin urmare au plecat mai departe. Văzând acestea, străjerii cetății au lăsat podul jos sărbătorind această „victorie”. Nu mult a durat această sărbătoare, fiindcă noaptea, când străjerii erau amețiți de vin și bere, tătarii s-au întors incendiind cetatea.
Acest fapt a deschis calea modernizării cetății și construirea acesteia sub formă heptagonală, precum și ridicarea unei catedrale gotice monumentale ce astăzi nu mai există.
Ofensiva otomană spre centrul Europei a ocolit Oradea, astfel că în momentul în care Buda a căzut în mâinile sultanului, Alba Iulia și Timișoara erau deja administrate de otomani, ceea ce făcea din Oradea o insulă non-otomană. Motivul poate fi și faptul că, deși și-ar fi dorit să cucerească cetatea iarna, când se aștepta ca sultanul să înghețe apa din șanțul cetății, șanțul era alimentat de pârâul Peța, care aducea apă termală. Motivul acesta a ținut până în 1660, când Ali Pașa pornește din Timișoara cu 45.000 de oșteni spre cetatea de pe Crișul Repede. 45 de zile a durat asediul, fiindcă turcii otomani nu puteau trece șanțul, iar tunurile așezate pe Dealul Ciuperca nu puteau dărâma zidurile masive ale cetății. Ghinionul a venit când pașa i-a luat ostatici pe băieții morarului, iar soția acestuia, fiind îndurerată, a negociat răscumpărarea fiilor prin dezvăluirea secretului cetății, indicându-le otomanilor locul unde să sape pentru a putea evacua apa din șanț.
Puțini știu asta, dar în momentul cuceririi cetății de către otomani, în interior se afla prima Biblie tradusă în limba maghiară. Dând dovadă de toleranță religioasă, Pașa i-a lăsat pe preoți să plece împreună cu Biblia.
În documentele de arhivă apar adesea dovezi ale propagandei pro-Napoleon și anunțuri de recrutare în armata napoleoniană pentru campania din Rusia. Pagubele produse orașului și gospodăriilor țărănești de către acești soldați nu au fost doar la plecarea în campanie, ci și la întoarcere.
Odată întorși din eșecul invadării Rusiei, o parte din soldații francezi au fost cantonați în cetatea din Oradea. Fiindcă nu prezentau un pericol direct, comandantul cetății le-a dat permisiune să plece în oraș. Șarmul și manierele francezilor au făcut furori printre femeile din oraș, însă problema a apărut când aceștia au destrămat familii. În acel moment, bărbații „păgubiți” s-au plâns episcopului, care, la rândul lui, i-a cerut comandantului să-i încarcereze pe acești soldați și să nu le mai dea voie în oraș.
De-a lungul istoriei sale, Cetatea Oradea a servit ca reședință a Episcopiei Romano-Catolice de Oradea (1092 – 1557), precum și drept cetate militară (1557 – 1857), aflându-se, pe rând, sub diferite administrații: maghiară/transilvăneană (1092 – 1660), otomană (1660-1692), habsburgică (1692 – 1918). De-a lungul secolelor, cetatea a fost asediată de: tătari (1241), turci (1474, 1598, 1658, 1660), răsculați transilvăneni (1290, 1514, 1664, 1703 – 1710), oștile Principatului Transilvaniei (1557, 1603), austrieci (1692). În ciuda multiplelor tentative, Cetatea a fost cucerită doar de trei ori.
În Cetate au fost înmormântate multe capete încoronate: Ladislau I al Ungariei, Andrei al II-lea al Ungariei (1235, dus ulterior la Agria), Ștefan al II-lea al Ungariei, Ladislau al IV-lea Cumanul (1290), regina Beatrix, soția lui Carol Robert de Anjou (1319), regina Maria de Anjou, soția lui Sigismund de Luxemburg (1396), regele-împărat Sigismund de Luxemburg (1437, singurul împărat romano-german înmormântat în afara Germaniei).
Marii căpitani de Oradea au jucat un rol important de-a lungul istoriei, Báthori István (Ștefan Báthory) ajungând în 1575 rege al Poloniei, iar Báthory Kristóf (Cristofor Báthori), Bocskay István (Ștefan Bocskai) și Rákóczi György (Gheorghe Rákóczi al II-lea) au ajuns principi ai Transilvaniei.
În afara funcției de apărare, zidurile Cetății au fost martore a numeroaselor târguri, ca de pildă Târgul de Sf. Maria, unde se schimbau mărfuri din Orient și din Occident și unde erau prezenți, spune un cronicar turc, Evlia Celebi, „40.000 de oameni”.
Din punct de vedere arhitectonic, Cetatea Oradea a cunoscut trei mari etape de dezvoltare. O etapă romanică, una gotică şi, în final, etapa renascentisto-barocă, cea care îşi pune amprenta asupra monumentului vizibil şi astăzi. Cetatea Oradea, în urma refacerii şi extinderii din secolele al XVI-lea şi al XVII-lea, capătă fizionomia tipică a unei fortificaţii de tip bastionar italian, cu bastioane de tip pană, fiind, de altfel, singura de acest tip din întreg estul european.
