Hauria estat poblada inicialmente per un poble agropastoral parent dels mandé soninke que van viure als promontoris rocosos de Tichitt-Oualata i Tagant a la moderna Maurtitània. Els Soninkés hi van construir una de les més antigues ciutats del continent africà. La ciutat actual va ser fundada al segle VII i integrada a l'Imperi de Ghana sent una ciutat de gran riquesa a causa del comerç. Va ser destruïda el 1076.

Va ser restaurada el 1224, tornant a ser un lloc comercial a les rutes del Sàhara, reemplaçant a Awdogast (Aoudaghost) com a lloc principal del sud del Sàhara per estació de termini de ruta i sent també un centre religiós. Al segle xiv fou part de l'Imperi de Mali. La ruta comercial començava a Sigilmasa i passava per Taghaza amb les seves mines de sal, acabant a Oulata. Ibn Batutta va fer aquesta ruta el 1325 quan va anar a Mali i va tardar 25 dies de Sigilmasa a Taghaza on va restar 10 dies. Després es va aturar tres dies a l'oasi de Tasarahla (probablement Bir al-Ksaib) on es preparava la darrera i més difícil etapa de 10 dies fins al final del trajecte; un home era enviat per davant per obtenir aigua i portar-la a la caravana a 4 dies del seu destí; en total el trajecte durava uns dos mesos. Els habitants eren musulmans i principalment de l'ètnia masufa; les dones gaudien d'independència i respecte; la ciutat la descriu breument: "La meva estada a Iwalatan (Oualata) va durar uns 50 dies i vaig ser acollit amb honor i allotjat pels habitants; era un lloc molt calorós on hi havia poques palmeres a l'ombre de les quals es cultivaven melons; l'aigua sortia de sota terra i hi havia bon nombre de cabres".

A la segona meitat del segle xv Tombuctú va substituir progressivament a Oualata que va declinar en importància. Fins aquest temps va conèixer el seu apogeu, quan caravaners i estudiosos hi feien etapa i l'anomenaven riba de l'eternitat. A l'inici del segle xvi fou visitada per Lleó l'Africà (vers 1509-1510) que la descriu al seu llibre "Descripció de l'Àfrica": "El regne de Walata és un regne petit i me condició mediocre comparat amb altres regnes dels negres; de fet només hi ha tres llocs habitats que són tres poblacions importants i la resta són cabanes en mig de les palmeres".

La ciutat vella cobreix una àrea de 6,00 x 300 metres, i una part està actualment en ruïnes. Els edificis d'arenes estan coberts de blanc i decorats amb dissenys geomètrics. La mesquita està avui dia a l'extrem est de la ciutat però antigament hauria estat rodejada d'altres edificis. L'historiador francès Raymond Mauny estimava la seva població a l'edat mitjana entre 2.000 i 3.000 habitants. Avui dia Oualata allotja un Museu del Manuscrit i és coneguda per la molt decorativa arquitectura vernacular. Fiu declarada Patrimoni de la Humanitat el 1996 junt a Ouadane, Chinguetti i Tichitt.