Restalaan was a long-time friend and second-in-command of the Prophet Velen who escaped with him and other eredar refugees - known henceforth as the draenei - from Sargeras' corruption of Argus. When the draenei settled on Draenor, Restalaan became the captain of the guard in the city of Telmor.
During a routine patrol, he and his men saved two future orc chieftains - Durotan of the Frostwolf Clan and Orgrim of the Blackrock Clan - from an ogre attack, and brought them to Telmor, revealing the hidden defenses of the city using a shard of the ata'mal crystal called Leafshadow and a phrase in his native tongue.
When the orcs began making war on the draenei, Durotan, now chieftain of the Frostwolves, met Restalaan and his men in battle. Restalaan defeated him, but spared his life because of an earlier incident in which Durotan spared and released Velen (on his way to Oshu'gun) from his custody. Later, Durotan - having remembered the incantation used to lower the invisibility shield that protected Telmor - was tasked by Warchief Blackhand to assault the city, as it was close to Frostwolf territory.
Locating the crystal and speaking the words Restalaan had used, Durotan revealed the city for the orcish invasion force, which proceeded to sack the city. With the city being torn apart around them, the two met again in combat, holding nothing back.
In the end, Durotan defeated and killed Restalaan - a deed that, along with the events that were soon to follow, would be a heavy burden on Durotan's conscience for the remainder of his life.
Restalaan was succeeded as Velen's lieutenant by Larohir.