Le origini di Urzulei si perdone nella notte dei tempi. L'uomo preistorico ha lasciato numerosi segni della sua presenza in questi luoghi. Basti pensare a Or Murales, uno dei villaggi nuragici meglio conservati della Sardegna con più di 100 capanne a forma di torre, realizzate in pietra bianca. Ma ci sono molte altre località significative che vantano passate presenze nuragiche: Su Nuragi’e Mont’Orosei, Su Mamucone e Su Nercone. Il territorio di Urzulei non è stato popolato solo dall'uomo dell'età nuragica: ci sono anche diversi resti dell'epoca romana e altomedievale. Si raccontano varie leggende sui villaggi di Thelevai, Siddie, Sa Pendula, S’arcu e Sa Idda, Mannorri, secondo le quali sarebbero stati distrutti da pestilenze, faide, antipatie campaniliste e questioni amorose. L’ultimo a essere scomparso tra questi villaggi è quello di Mannorri, di cui le ultime notizie risalgono alla fine del 700, quando ospitava una quarantina di abitanti. La leggenda vuole che a porre fine al piccolo villaggio sia stato un bacio rubato a una bellissima fanciulla mentre usciva con la madre dalla chiesa dell’Angelo, da parte di uno dei tanti pretendenti. La fine dell’antico borgo fu decretata da una serie di scontri di cui quello finale pare sia stato decisivo, con circa 20 morti. Della chiesa dell'Angelo non rimane alcuna traccia.
L'attenzione degli storici alto medioevali è rivolta invece ai ruderi di una chiesa (il Monastero di Olefani) nella zona Su Murtargiu sotto genna Silana, che potrebbe essere appartenuta all'ordine latino dei Benedettini cassinesi di Monte Cassino.
Nel periodo tra le due guerre il lavoro di Ugo Pellis nel 1934, è stato fondamentale perchè ci potessero pervenire le testimonianze di quel periodo.

Derivazione del Nome

Ci sono diverse interpretazioni riguardo all'origine del nome del paese. Secondo qualche studioso, in modo particolare Wagner, il nome di Urzulei deriverebbe dalla parola greca Urthula, cioè saltapariglia, che in dialetto è Teti, ovvero pianta da siepe.
Secondo altri studiosi, come Massimo Pittau, sarebbe di sicura matrice nuragica, secondo altri ancora di origine etrusca.
In una vecchia campana della chiesa di Sant'Antonio del 1556 che fu rifusa alcuni anni dopo, il paese figura col nome di Orcqullè, che non sembra avere molto in comune con Urthula: questo fa pensare che la soluzione della pianta da siepe sia poco realistica. Di fatto, quindi, non ci sono notizie etimologiche certe.