From A Wiki of Ice and Fire
The Red Waste is a region on the continent of Essos. A forbidding landscape of stunted trees, devil grass and ancient ruins, which stretches southwards for hundreds of miles.
The Red Waste located South of the Dothraki Sea and Lhazar, the land of the Lhazareen. East of slaver cities and their hinterlands and north of the fabled city of Qarth. It is a land of low hills, barren windswept plains, dry rivers and red parched soil. Where the necessities of living are hard to come by. There are few things in the red waste that will support life. There is little forage and shallow, bitter, stagnant pools of water. Wood is hard to find, with the best being gnarled and tough.
Within the Red Waste are four abandoned cities, Vaes Tolorro, and three others called Vaes Orvik, Vaes Shirosi and Vaes Qosar. To the south of Vaes Tolorro the waste continues to the sea. To the southeast lies Qarth.
A Game of Thrones
Here Khal Drogo who lead his Khalasar into the Red Waste, succumbs to his wounds and his wife Daenerys builds his funeral pyre, sacrificing Mirri Maz Duur and manages to hatch her dragon eggs to beget dragons onto the world again.
A Clash of Kings
Following the comet, Daenerys leads her much-reduced khalasar across the red waste, losing many of the weaker members of her group. They eventually stumble upon an abandoned city, which they name Vaes Tolorro and rest while Dany sends her bloodriders to scout and explore. Eventually, from the southeast, Jhogo returns with envoys from Qarth.