Leeb kam bereits früh nach Wien, wo er 1793 in den Konzeptsdienst der Stadt Wien als Magistratssekretär eintrat. In der Zeit der französischen Besatzungen Wiens durch napoleonische Truppen erwarb er sich Verdienste, so 1799 als Magistratsrat, als Mitglied der landesfürstlichen Militär- und Zivilkommission und als Oberstwachtmeister. Besonders bemühte er sich um den Ausbau des Bürgermilitärs. 1810 wurde Leeb geadelt.
Die Bestellung zum Bürgermeister erreichte Leeb durch eine Reihe von Zufällen. Im September 1834 wurde Bürgermeister Anton Lumpert zum Rücktritt veranlasst. Der eigentlich als Nachfolger vorgesehene Ignaz Czapka war ein Protegée von Kaiser Franz I. gewesen, der aber verstarb. Somit hatte Czapka unter dem neuen Kaiser Ferdinand I. keine Chance mehr auf eine Bestellung. Dadurch fiel die Wahl nun auf Anton Josef Leeb mittels allerhöchstem Entschluss vom 31. März 1835 und Regierungsdekret vom 7. April 1835.