La région connaît un peuplement ancien. On peut considérer que Tozeur est d'origine berbère même si la tradition locale ne le revendique pas. Elle devient très vite un centre actif du commerce caravanier transsaharien fréquenté par les Carthaginois Les Romains s'y installent en 33 av. J.-C., la ville prenant le nom de Thusuros, mais les vestiges de cette époque sont rares. La ville devient un poste sur le limes saharien spécialisé dans le commerce des dattes mais aussi des esclaves (sur la voie romaine allant de Gabès à Biskra). De l'influence chrétienne, il subsiste les vestiges d'une église reprise ensuite par la mosquée al-Kasr (située à Bled al-Haddar).Au XIIIe siècle, la ville devient musulmane avec l'arrivée des Hafsides et est dotée de 2 mosquées. Elle se développe en dehors de sa palmeraie et connaît un grand essor économique jusqu'à son apogée au XIVe siècle.

La municipalité est créée le 23 juillet 1888.Tozeur reste une ville de destination ou de passage pour de grandes caravanes jusqu'au XIXe siècle, époque où elle se replie sur sa vocation de production de dattes. Avec le développement des villes minières voisines de Métlaoui et Redeyef, vers les années 1950, Tozeur voit sa population diminuer. À la production de dattes, dont les célèbres deglet nour, s'ajoute plus récemment le développement du tourisme saharien. L'aéroport international de Tozeur-Nefta, mis en exploitation en 1980, est voué aux charters et dessert tout le sud du pays.On doit à l'homme de lettres et mathématicien Ibn Chabbat (né à Tozeur et mort en 1282) d'importants travaux sur la culture du palmier et l'amélioration notable d'un système de répartition des eaux de l'oasis : son plan du XIIe siècle est exposé au Musée des arts et traditions populaires. Tozeur est par ailleurs la ville natale du poète Abou el Kacem Chebbi