The order was originally founded by some of the vrykul who stayed behind in Tirisfal Glades after the death of Tyr, with the purpose of safeguarding the tomb endlessly.
These vrykul, knowing that they would not live forever, started inducting some of the fledgling humans into their ranks. The vrykul taught the human members of Tyr's Guard the history of the fallen keeper Tyr, his tenets of self-sacrifice and justice, and the truth of what laid within the tomb.
The only time they ever failed their task was when the legendary human king Thoradin, obsessed with his race's history after abdicating his throne, eventually managed to breach the tomb. Tyr's Guard knew that Thoradin's magi had broken the tomb's wards and its members made a vow that they would not enter the catacombs again, for fear that further meddling could awaken the C'Thrax buried inside and unleash its evil on the world.
For thousands of years, Tyr's Guard continued its sacred duty. New members came and went, and over time they adopted more techniques to help them protect Tyr's tomb. In particular, the defenders felt an affinity toward paladins, holy warriors who arose to battle the orcish Horde in the Second War. The members of Tyr's Guard learned how to wield the Holy Light, and they became mighty paladins. Yet even this newfound power could not save the order from the undead Scourge.
When the Scourge swept over the human kingdom of Lordaeron, Tyr's Guard crumbled. Only a few brave members, led by a paladin named Travard, remained to uphold their ancient vows.