T-canon sources (the Clone War animated series) paint them as an already existing group of elite clones serving with Jedi General Anakin Skywalker and Clone Captain CT-7567, nicknamed "Rex."
Because of Skywalker's less than orthodox leadership techniques and the operational latitude he gave the soldier's of the 501st, they were able to complete extraordinary missions under difficult circumstances, establishing themselves as a crack team.
Among the 501st's earliest battles was the Battle of Christophsis, where they served under Skywalker, Captain Rex, and High Jedi General Obi-Wan Kenobi. Based out of Crystal City, the 501st troops managed to recapture Christophsis from the Confederacy, beating back Separatist General Whorm Loathsom's multiple assaults. However, Loathsom soon deployed a deflector shield to protect his battle droid troops, and the clone troopers were forced to pull back and defend the Republic's heavy cannons. After Skywalker and his newly assigned Padawan, Ahsoka Tano, destroyed the shield generator, the heavy cannons annihilated the droids and forced the Separatists to surrender. -- Wookiepedia > 501st Legion