Mahone utexaminerades 1847 från Virginia Military Insitute. Han var sedan verksam inom järnvägsbranschen och avancerade till verkställande direktör för Norfolk & Petersburg Railroad. Han deltog i amerikanska inbördeskriget i sydstatsarmén och befordrades till generalmajor. Mahone var på nytt verksam inom järnvägsbranschen efter inbördeskriget. Han var verkställande direktör för Atlantic, Mississippi and Ohio Railroad.
Populistisk politiker
Mahone var en av grundarna för det populistiska Readjuster Party som strävade efter omfördelning av egendomen. Partiprogrammet betonade speciellt vikten av utbildningspolitiken och partiet stöddes av både vita och svarta. Mahone efterträdde 1881 Robert E. Withers som senator för Virginia. Mahones parti vann dessutom guvernörsvalet i Virginia 1881 och William E. Cameron kunde tillträda som guvernör den 1 januari 1882. Harrison H. Riddleberger tillträdde 1883 som senator och då hade Readjuster Party nått sin höjdpunkt i och med att båda senatorerna för Virginia och dessutom delstatens guvernör kom alla från samma parti.
Partibyte
Mahone och Riddleberger bytte 1885 parti till republikanerna och demokraterna lyckades relativt snabbt återfå makten i Virginia. Mahone efterträddes 1887 som senator av John W. Daniel.