During the War of Power, there were two plans as to how to defeat the Shadow; one was the plan supported by Latra Posae Decume, a female Aes Sedai of great strength and prominence to use the ter'angreal access keys to wield the One Power through the giant sa'angreal in order to defeat the forces of the Shadow and to erect a barrier around Shayol Ghul until a way to deal with the problem could be devised. Using the statues directly was impossible due to the massive amounts of the One Power and due to the difficulty of transporting them to the field of battle.
When the access keys and the Choedan Kal were lost to the advancing armies of Sammael, Demandred and Be'lal, Lews Therin and the Hundred Companions felt they had no choice but to employ their alternative plan of sealing the bore.
The Choedan Kal remained unavailable until recently; the female statue is half-buried on the Sea Folk island of Tremalking and the male statue is being excavated near the village of Tremonsien, in Cairhien. Rand al'Thor first encountered the male statue while en route to Cairhien, following his trip through the Portal Stones. At the time, Selene (Lanfear in disguise), who was with him, panicked and berated Rand about his ignorance in the One Power when the allure of the sa'angreal makes Rand attempt to channel through it without one of the access ter'angreal.
Egwene al'Vere (in Tel'aran'rhiod), and then later Nynaeve al'Meara (in the waking world) found the top half of a broken female access key in the Panarch's Palace in Tanchico, but it did not allow full access to the power of the female sa'angreal, and could potentially harm the saidar channeler attempting to use it.
While in the Aiel Waste, Rand encountered the male and female access keys in Rhuidean. Rand discovered that Asmodean was in Rhuidean attempting to find an access key ter'angreal which he thought was there. Rand battled Asmodean for control of the key for the male part of Choedan Kal and it revealed that two men touchting the same key can channel through the sa'angreal at the same time, both controlling half of the power equally balanced. He could only won over Asmodean with the extra help of his fat bald man angreal.  From this point, Rand had the two access ter'angreal in his possession. Lanfear tried to tempt him by saying a man and woman using the Choedan Kal together could challenge the Dark One, and maybe the Creator himself. It is interesting to note however, that Lews Therin believed that brute force could not stop the Dark One from breaking free, so the truth of Lanfear's statement remains to be determined.
Asmodean discreetly referred to the sa'angreal as the only chance Rand has of winning the Last Battle. It was about this time that Rand began to toy with the idea of using the sa'angreal to cleanse the taint of saidin. Originally, he had planned to use Callandor for the deed, but after Cadsuane Melaidhrin informed him of Callandor's flaw, he realized the Choedan Kal were his last hope.
During the Battle near Shadar Logoth, Nynaeve al'Meara and Rand linked outside Shadar Logoth, and tapped the Choedan Kal through the access ter'angreal. Rand was successful in cleansing the taint from saidin, but in the attempt, the female access key was destroyed as well as the sa'angreal itself. The male counterpart remained in Rand's possession. Some comments by Lanfear suggest the female counterpart could be used repeatedly if the channeler was as strong as Lanfear.
The statues glowed brightly during their intensive use to clean saidin (which appears to be typical behavior for a sa'angreal in use). The native people on Tremalking apparently saw the glowing female statue's orb as a herald to the end of the "Time of Illusion," and shortly thereafter all of the island's inhabitants committed mass suicide.
After Semirhage's failed attack on Rand using the Domination Band, he recovered the male access key and took to carrying it around, almost using it on Tuon and Seanchan holdings in the Westlands. Cadsuane considers this Rand's temptation by the access key, and its impact on Rand's psychology, the main reason for stealing Domination band from her box rather than from Seanchan. After Rand's fulfilment of a part of the Prophecy of the Dragon, he draws in as much power as he can through the sa'angreal and drives it back through itself, purposely obliterating it.