He was then elected Mayor of Richmond in 1998 and was in that position until being elected Lieutenant Governor of Virginia in 2001.
Ia kemudian terpilih sebagai Wali Kota Richmond pada tahun 1998, menjabat di posisi itu sampai akhirnya ia terpilih menjadi Wakil Gubernur Virginia pada tahun 2001.