Husene i Vognmandsgade er formodentlig nyopført i 1730’erne.
Gaden hed tidligere Vognmagergade, men det nuværende navn skyldes, at der gennem årene har boet flere vognmænd her. Disse vognmænd havde deres køretøjer parkeret i en indhegning på Badstuevælen.