Being a practical man, Erlembaldo’s first step was to go to Rome and confirm papal backing for the reform enterprise. What he found was heartening.
The man who reigned as Pope at this point, under the name of Alexander II, was Anselmo of Baggia, a committed reformer and an original member of the pataria, as well as one of the Milanese clergy’s original four recommendations for Archbishop, who had been passed over by the Emperor in favor of the corrupt Guido.
Guido had attempted to neutralize Anselmo by sending him far away across the Alps, to the court of Emperor Henry III. The tactic had backfired stupendously. Anselmo had been able to spread his reformist ideas across a wider area, and among the friends and allies he gained was the redoubtable Hildrebrand—also a dedicated reformer, and a power behind the papal throne. In the course of time, Hildebrand had succeeded in getting Anselmo installed as Pope.
Anselmo/Alexander needed no education or persuasion on the need to deal firmly with Guido. He assured Erlembaldo that he would back him in the actions that needed to be taken.
Armed with papal authority as well as his own military skills, Erlembaldo returned to Milan and set to work.
His first job was to develop a force capable of physically standing up Guido. Normally only the aristocracy had the armor, weapons, horses, and training required to exert significant force. Most of Milan's feudal elite backed Guido, however. It therefore fell on Erlembaldo to show the non-aristocratic people of the city how to fight effectively for themselves.
Erlembaldo led his improvised army in deposing deposing key abbots, then moved against Guido himself. He accused Guido of taking false oaths, since he had not taken action against simony in his province. Upon Erlemaldo's and Arialdo’s recommendation, Pope Alexander excommunicated the Archbishop in 1066 for his repeated lapses.