Hi va haver assentaments de poca importància des de fa sis mil anys; s'hi han trobat restes de l'edat del coure, de la cultura argàrica, dels oretans, d'un oppidum ibèric (Iltiraka) que va dependre de la colònia romana de Salària, dels visigots i hispanoromans, tots a la zona on avui dia hi ha l'Alcàsser, excepte els ibèrics (zona avui coneguda com a Úbeda la Vieja), que es troben al lloc de la desembocadura del riu Jandulilla al Guadalquivir. Durant l'Imperi Romà, Iltiraka s'havia convertit en Betula (Baetula), sent centre de població disseminada per la comarca. Els vàndals al seu pas van assolar la regió i els habitants es van concentrar en la que fou coneguda com a Bétula Nova.

La ciutat com a tal hauria estat fundada per Abd-ar-Rahman II (822-852) i acabada sota l'emirat del seu fill Muhàmmad I (852-886) pel governador de Jaén (Jayyan) Haixim ibn Abd-al-Aziz. Va portar el nom d'Ubbadha i fou coneguda també com a Ubbadhat al-Arab ('dels àrabs') a causa de l'existència d'un altra ciutat amb el mateix nom (Ubbadha Farwa) a la cora d'Ilbira (Elvira). Tenia com a finalitat controlar els mossàrabs de Baeza; la població va ser dotada amb unes muralles defensives i va agafar certa importància per la fertilitat dels seus camps (vinya i cereals, principalment blat i civada) i la seva artesania i comerç, sense deixar de ser una vila mitjana. Un tal Ibn Maymun s'hi va revoltar durant el regnat d'Abd-Al·lah ibn Muhàmmad (888-912). El 913 Abd-ar-Rahman III va sotmetre els rebels de Jaén i va poder dominar tota la cora (kura) però el 916/917 es va apoderar de la ciutat el fill d'Umar ibn Hafsun, Sulayman ibn Umar, que finalment es va haver de sotmetre a l'emir cordovès (després califa) un any després.

A la caiguda del califat a Còrdova als primers anys del segle xi, Jaén, Baeza i Úbeda devien passar sota control dels Banud Dhi l-Nun, que abans del 1035 van prendre el poder a la taifa de Toledo; en tot cas estava en poder d'al-Mamun de Toledo quan aquest va morir el 1075, però llavors va caure en mans dels abbadites de Sevilla amb tota la vall del Guadalquivir. Sevilla va conservar el territori fins que al seu torn fou ocupada pels almoràvits el 1091. Úbeda també fou dominada per aquestos fins al final del seu domini, excepte el 1144 quan Zafadola (Àhmad ibn Abd-al-Màlik Sayf-ad-Dawla) antic emir dels Banu Hud, que havia governat a Rueda de Jalón del 1130 al 1139 quan va cedir el territori a Castella a canvi d'un important feu a Toledo, i que es va posar al front de l'antiga noblesa reial i els seus partidaris d'arreu a l'Àndalus, en contra dels almoràvits, ocupant Qurtuba, Jayyan, Granada, Mursiyya (1145) i Balansiya (1146), però en la batalla d'al-Lujj contra els cristians, el 5 de febrer de 1146, fou derrotat i mort. No s'esmenta Úbeda però segurament la va ocupar junt amb Baeza quan va dominar Jaén. Retornada als almoràvits el 1146, el seu darrer representant, Yahya Ibn Ghaniya, va haver de cedir-la junt amb Baeza a Alfons VII, que les va ocupar (junt amb Almeria) fins que els almohades les van recuperar el 1157. El 1159 Muhàmmad ibn Mardanix (el Rei Llop) i el seu sogre Ibrahim ibn Hamushk, de Jaén, van ocupar Baeza i Úbeda el 1159. El 1165, quan Ibn Mardanix va intentar ocupar Còrdova, es va posar en marxa a Sevilla un formidable exèrcit almohade vingut del Marroc i reforçat a la Península, sota direcció de Uthman, el governador almohade de Còrdova. Els almohades van conquerir Andújar, Baeza, Baza, Caravaca, Cuéllar i Vélez-Rubio, i finalment el Rei Llop i el seu exèrcit, reforçats amb 13.000 cristians, patiren una indiscutible derrota en el lloc on la vall del Guadalentí s'uneix a la vega murciana (15 d'octubre de 1165). Les inexpugnables muralles de la ciutat de Madina Mursiyya varen protegir l'emir, les restes del seu exèrcit i la població civil, però la rica horta i les sumptuoses mansions d'esbarjo dels nobles murcians van quedar a mercè dels invasors, que van destruir i saquejar tot el que van voler: la resistència de Montagut li valgué ser assolada. Aprofitant la derrota patida per Ibn Mardanix davant dels almohades, el rei Alfons II d'Aragó va obrir un nou front per a la conquesta cristiana, avançant pel riu Túria i pel riu Guadalop.

El juny de 1169 Ibn Hamushk va adoptar les doctrines almohades i va sotmetre els seus dominis als almohades, entre els quals Úbeda. El poder almohade va començar a tirar enrere després de la batalla de les Navas de Tolosa (per als musulmans, batalla d'al-Ukab) el 1212, coneguda també com la de Úbeda. Al final de la batalla els cristians van entrar a Úbeda, que no havia estat evacuada pels seus habitants (com sí que ho havia estat Baeza); molts foren massacrats i altres convertits en captius, entre els quals el cadi local Abu l-Hasan Ali ibn Katral, que fou alliberat i va ser cadi en diverses viles de l'Àndalus i el Magreb (va morir a Marràqueix). Els cristians no obstant no van restar a Úbeda, que van abandonar per raons que no apareixen clares i varien segons les fonts.

Després de la conquesta final de Baeza pels castellans, el 1233, Úbeda fou conquerida també definitivament per Ferran III de Lleó i de Castella després d'un llarg setge iniciat el 6 de gener de 1233 i acabat el juliol del mateix any. La ciutat es va rendir, ja que no podia rebre auxilis d'al-Mutawakkil Ibn Hud, revoltat contra els almohades i reconegut per gran part de l'Àndalus; la població musulmana, d'acord amb el pacte de rendició, va poder abandonar la ciutat amb els seus bens, escortats i protegits pels castellans sota garantia del rei.

El 1367-1368 durant la guerra civil entre Pere el Cruel i Enric de Trastàmara, el rei Muhàmmad V de l'Emirat de Gharnata va ocupar Jaén i Úbeda (1368) però no va poder conquerir les ciutadelles de les dues ciutats i per tant no les va poder conservar. Pel seu costat diverses expedicions castellanes van sortir d'Úbeda per assolar terres granadines. Després del 1492 no va tardar a eliminar les muralles (el 1506). El 1526 fou visitada per l'emperador Carles V del Sacre Imperi Romanogermànic. Fou capçalera d'una jurisdicció que anava de Torres de Acún (Granada) fins a Santisteban del Puerto, passant per Albánchez de Úbeda, Huesa i Canena (a la meitat del segle xvi també incloïa en el seu partit jurisdiccional les viles de Cabra del Santo Cristo, Jimena, Quesada, Peal, Sabiote i Torreperogil. Aquesta condició de capital d'un territori extens, i la pau, va portar a un període de prosperitat i creixement demogràfic, i la ciutat va assolir els 18.000 habitants, i esdevingué una de les més poblades de tota Castella. També el bisbat d'Úbeda fou dels més importants i rics.

Però els segles xvii i xviii van ser de decadència; una pesta el 1681 (ja n'hi havia hagut una el 1585), el terratrèmol del 1755 (seqüela del terratrèmol de Lisboa del mateix any), l'expulsió dels moriscs, l'augment dels impostos per finançar guerres, la competència de productes d'altres llocs, la corrupció, el poder del clergat, la inflació, les lleves militars, l'emigració a Amèrica i altres factors foren la causa d'aquest retrocés; la guerra de Successió del 1700 va contribuir també a la decadència local en haver d'aportar cavalls, armes, diners i soldats; la ciutat estava al límit i es va revoltar el 19 de març de 1706 contra els recaptadors reials. La ruïna era total i molts pobles que depenien d'Úbeda se'n van separar.

Després de 1735 es va tocar fons i encara que el terratrèmol de 1755 va destruir un nombre considerable de cases, la ciutat es va recuperar lentament, però llavors va arribar la Guerra del Francès; Úbeda va estar en mans de forces franceses al servei del rei Josep del 1810 al 1813, i la ciutat va tornar a arruïnar-se de manera que no hi havia ni bèsties per treballar els camps, ni llavors, ni elements per a la subsistència. Fins a la meitat del segle no va començar a remuntar, tot i que no va gaudir dels beneficis de la revolució industrial. El caciquisme i la falsificació electoral van esdevenir la norma.

Durant la lluita del govern contra els rebels feixistes (1936-1939) la violència i la repressió va afectar la ciutat, que no obstant no fou part del front de guerra. Després de la guerra van venir els anys de la gana, i l'emigració massiva cap a Catalunya i Euskadi.

El 3 de juliol de 2003 fou designada, junt amb la veïna Baeza, Patrimoni de la Humanitat.