Per les restes arqueològiques es coneix que, en època imperial romana (s. I dC), un fort cinturó emmurallat defensava un petit altell en el qual més tard es fundaria la vila medieval. A més, al voltant del nucli urbà actual s'han trobat restes de viles romanes. Sant Isidor de Sevilla, en la seva Historia de regibus gothorum, ens oferix la primera referència escrita sobre Olite: segons el citat bisbe de Sevilla, el rei got Suintila va fundar la ciutat d'Oligicus en el 621 i la va tornar a fortificar per plantar cara als vascons. Per un privilegi donat a Estella en l'any 1147, García Ramírez el Restaurador, rei de Navarra, va atorgar a Olite el seu primer fur, el Fur dels francs d'Estella, donant-los en la mateixa ocasió terres de cultiu.

La promulgació del fur va produir una ràpida expansió d'Olite. Com a instrument jurídic, va proporcionar a la població un exercici social propi (el terme municipal), jurisdicció privativa i notables avantatges fiscals, així com elements i quadres propis de govern de la vila. El 17 de març de 1266, a Saint Denis, Teobald II de Navarra concedeix a Olite quinze dies de fira anual, com "les tenen els burgesos d'Estella", que començà l'1 de maig. Des d'aquest mateix any es van efectuar corts a Olite. El gener de 1302, Felip i Joana, reis de Navarra, en respondre a les peticions d'Olite, varien la data de la fira anual, n'assenyalaren el començament el 2 de novembre. Després de segles foscos, la vila d'Olite va començar una etapa d'esplendor durant la baixa edat mitjana, en ser triada com una de les seus favorites dels reis de Navarra. A partir del s. XV el rei Carles III el Noble i la seva esposa Elionor de Trastàmara van començar la construcció de l'esplèndid palau Reial de Navarra a Olite, reflex de la lluentor de tota una època.

És capital o cap de la batllia del seu nom, creada per Carles III el Noble el 1407. Felip IV li concedeix el títol de ciutat el 1630. Des dels seus brillants moments en el s. XV i fins al s. XIX, Olite experimenta un eclipsi polític i un fort descens demogràfic. Al començament del s. XIX, cal destacar els greus problemes dels comunals i l'interessant fenomen del cooperativisme agrari (a Olite es va fundar la primera cooperativa de Navarra i tercera de l'estat).