The Aiel War was a conflict between the Aiel and a coalition of the nations on the other side of the Dragonwall. It began when Laman cut down Avendoraldera, to make a throne as part of one of his schemes. The Aiel, who had given Cairhien the sapling five hundred years earlier as thanks for their ancestors actions during the Breaking (TSR, Ch. 34) took offence and launched an attack in the spring of 976NE, with the intent of executing Laman. It was composed of just four clans, the Nakai, the Ryne, the Taardad and the Shaarad, under the leadership of Janduin, the Taardad clan chief (TWoRJTWoT, Ch. 14).
Cairhien was captured and burnt, except for the libraries in just a few months. Over the course of three years, the battles moved around, more and more nations sending men to join the fight. The battles followed Laman until the Aiel were able to kill him at the Battle of the Shining Walls at Tar Valon (TWoRJTWoT, Ch. 14), where a force of around 80,000 Aiel faced twice that number of Wetlanders. After killing Laman, the Aiel retreated, having done what they came for. Though many believe they were then forced back, in reality, only a harrying force followed them.
Since then, Aiel have held Cairhienin in contempt, referring to them as "Oathbreakers" or "Treekillers' (TFoH, Ch. 20). After Laman was killed, his sword was taken back to the Waste as proof he was dead. It then passed through many hands, no Aiel wanting to touch it long enough to even remove the jewels from the scabbard, until Aviendha gave it to Rand (TFoH, Ch. 21).