Johnson var född i North Carolina i fattiga omständigheter. Sedan familjen flyttat till Tennessee utbildade sig Johnson till skräddare och ägnade sig först åt lokalpolitik. Han var ledamot av unionens representanthus 1843–53, guvernör i Tennessee 1853–57 och senator 1857–62. Johnson var demokrat men bestämd motståndare till sydstaternas separatism.