Archeological excavations have shown that the area of Tudela has been populated since the lower paleolithic era. The town of Tudela was founded by the Romans on Celt-Iberian settlements. Since then the town has been inhabited continuously. The Roman poet Marcus Valerius Martialis (Epigrams Book IV, 55) "recalls in grateful verse" the town of Tutela compared to his native Bilbilis. The city was later taken by the Arabs during the Umayyad conquest of Hispania and became the Muslim emirate of Al-Hakam I in 802 under Amrus ibn Yusuf al-Muwalad.

At the beginning of the 9th century, the strategic importance of Tudela as a site on the river Ebro was enhanced by historical and political circumstances. It became the base of the Banu Qasi family of Muladis, local magnates converted to Islam that managed to stay independent of the emirs, establishing an on-off alliance and close ties with the Kings of Pamplona over the next century. With the power of the Banu Qasi fading at the onset of the 10th century, the town fell under the influence of the rising Caliphate of Cordoba and had to come up against a more aggressive policy on the part of the new dynasty ruling in Pamplona, the Ximenes, who had set up close ties with their neighbouring Christian kingdoms.

The town was used by Muslims as a bridge-head to fight against the expanding Kingdom of Navarre. When Christians under Alfonso the Battler conquered Tudela in 1119, three different religious communities were living there:

• the Muslims,
• the Mozarabs
• the Jews

In the aftermath of the conquest, community relations appear to have been strained and Muslims were forced to live in a suburb outside the town walls, whereas Jews continued to reside inside the walls . The co-existence of different cultures is reflected in Tudela's reputation for producing important medieval writers such as Al-Tutili. In 1157 the English scholar Robert of Ketton, first translator of the Koran to a Western tongue (Latin), became a canon of Tudela.

The Jews were banished in 1498 (the expulsion from Navarre occurring slightly later than in the rest of Spain). Muslims and Moriscos were expelled in 1516 and 1610 respectively. There are still examples of Islamic-influenced architecture in the city - the style the Spanish call Mudejar; but the principal mosque was handed over to The Church in 1121, and by the end of the 12th century construction of the cathedral had begun.

Later Tudela became an important defensive point for the Kingdom of Navarre in battles with Castile and Aragon. Tudela was an Agramont party stronghold and actually the last Navarrese one to surrender to Ferdinand II of Aragon's Aragonese troops in the initial 1512 Spanish invasion of Navarre, only doing so to avoid futile bloodshed, Spanish pillaging and further confiscations to town dwellers, after the Navarrese king failed to send a relief force.

At the end of the 17th century, a new public square was built, called Plaza Nueva or Plaza de los Fueros, which became the main city square. On 23 November 1808, Napoleon Bonaparte's Marshal Lannes won the Battle of Tudela in the Peninsular War. The train station was built in 1861, which, together with the agricultural revolution, resulted in a new period of expansion for the city.

Main sights include:

• The Cathedral (12th-13th centuries). It includes examples of Romanesque architecture, such as the Puerta del Juicio, or Door of the (Last) Judgement. There are some Gothic influences and also Baroque additions to the building.
• Church of Magdalene (12th century), in Romanesque style.
• Church of San Nicolas (12th century).
• Church of San Jorge (17th century), in Baroque style.