Encara que hi ha restes d'habitació prehistòrica, la ciutat té el seu origen en l'època de dominació romana, quan era coneguda amb el nom de Tutela.[2] Fou una antiga ciutat delsvascons[2] —ciutat fundada probablement perRoma, i poblada perceltibers, vascons,ibers i d'altres grups, àmpliament romanitzats. De l'època romana s'han trobat nombrosos vestigis, incloent-hi una alcassaba o ciutadella a la zona occidental. Situada a la riba dreta de l'Ebre i a l'est dels Montes de Cierzo —en un camp regat per alguns barrancs (Las Limas i San Gregorio), pel rierol Mediavilla i pel riu Queiles, que desemboca en l'Ebre, a la confluència del qual va sorgir la primitivaTutela. El pont de pedra que travessava l'Ebre va ser construït pels romans, i es prolongava per una via cap als dos costats.
Sota els àrabs fou centre d'una kura que incloïa Arnedo, Alfaro,Borja, Calahorra, Najera,Tarassona i Viguera. Va formar part de la Marca Superior i fou part dels dominis de la família delsBanu Qasi. El comte Casius apareix abans del715 i va ser client del califa omeia i tenia les seves terres a la regió.Al-Hàkam I (796–822) hauria erigit el poble en vila amb el nom de Tutila. Des del 813 fou governava de manera continuada pels Banu Qasi. L'any862 a la mort de Musa ben Musa, poderós magnat que es feia dir el tercer rei d'Hispània, els seus dominis, després d'un breu període indivís, es van repartir entre els seus quatre fills. Fortun va rebre Tudela que després va passar al seu fill, per retornar de seguida al fill del fill gran de Musa ben Musa, Muhammad ben Llop conegut per Ababdella, senyor deViguera, que també va recollir l'herència del germà Ismail (Saragossa). El seu fill Llop va ocuparToledo del897 al898 i altra vegada el903 i la va cedir al seu germà Mutarrif, i d'aquest va passar al seu nebot Muhammad ben Ismail (fill d'Ismail de Saragossa) que la va perdre un any després. Va morir el907 i el va succeir el seu germà Abdallah ben Muhammad, que va perdre els darrers dominis enfront delsBanu Tawil d'Osca cap al908 o909 que no la devien conservar gaire temps. No és clar si els Banu Qasi hi van exercir el control fins al 924[3] quan Abd al-Rahman III va donar el govern de Tudela a Muhammad ibn al-Ankar, que era governador de Saraqusta, de la família deltugibites en mans dels quals es va conservar després de la caiguda del califat.