Rhuidean is a city in the Aiel Waste built by the Jenn Aiel, some time after the Breaking of the World, but before the Trolloc Wars. It was a large unpopulated city, but smaller than Tear and Caemlyn. The buildings are all majestic palaces, with many unfinished. There is a great plaza in the center of the city filled with hundreds of objects of the One Power. Avendesora grows at the very center.
After the Breaking of the World, the Aiel, like all peoples, wandered the land looking for safe refuge from the depredations of the insane male channelers. This eventually brought the Jenn Aiel to the Three-fold Land in the first place, and with the aid of the Aes Sedai who accompanied them, built the first and only city there, which they named Rhuidean. Rhuidean was built according to the memories of the great cities before the Breaking, and thus had wide avenues and great towers and palaces. These were never finished, however, for the Jenn eventually died out. They also presumably put up the barrier that surrounded the city, making channeling difficult and covering the city in thick fog.
The city was never fully and properly inhabited, and was left abandoned after the last of the Jenn Aiel died. The items of the Power they had sworn to protect long ago were left behind, scattered about in the central plaza.
However, the Aes Sedai who accompanied the Jenn had made sure that the hardier warrior Aiel who protected the Jenn would not forget where they came from. They visited the Wise Ones of the Aiel in their dreams, and told them of the Prophecy of Rhuidean, and arranged a system to maintain cohesion of memory among the Aiel. Before the Car'a'carn came, only sept-chiefs who were chosen to become Aiel clan chiefs and apprentices of the Wise Ones would venture to the empty city, and would there learn the truth of their history, in the ter'angreal left there for that purpose. All others were forbidden to enter.
In 999 NE, Rand al'Thor accidentally destroyed the barrier surrounding Rhuidean and badly charred Avendesora, after a battle of the One Power with the Forsaken Asmodean. This also created a great rift in the earth, causing an underground lake to flow to the surface. Before leaving the Aiel Waste, Rand al'Thor channeled the fountains of Rhuidean to once again flow, and moved Aiel into the city. Rhuidean is now being slowly populated and rebuilt. Plans to involve Ogier in the reconstruction have been talked about. If this effort is successful, it will be the only city in the entire Aiel Waste.