Rådhusgade blev døbt i 1856, da Horsens havde fået sit nye Rådhus (1854-1855). Før den tid hed gaden Provstegyde. Provstegyde ses første gang nævnt i dokumenter fra 1624, hvor “Rasmus Rasmussen i Provstegyde” lod sin kone begrave.
Tæt ved Provstegyde gik Horsens gamle befæstningsværker. Vestvolden strakte sig fra et punkt vest for sydenden af Lille Smedegade over Mælketorvet samt arealerne mod vest for Graven og Provstegyde til åen.
Ifølge Resens Atlas var Provestegyde allerede helt bebygget i 1677, men i dag er Rådhusgade kun bebygget med offentlige institutioner.