La ciutat es va originar al voltant del castell de Skanderborg, començat el 1171 durant el regnat de Valdemar el Gran, situat en una petita illa al llac Skanderborg, una bona localització defensiva a la ruta d'Århus (avui dia ja no és una illa i tanca l'estany de Lillesø, literalment el llac de l'illa). Skanderborg va aconseguir el títol de ciutat el 1583 al mateix temps que el rei Frederic II completava el castell. El castell va ser enderrocat el 1720 i només s'ha conservat la capella amb la seva torre rodona. El 26 de juny del 1712 el rei Frederic IV es va casar amb la seva segona esposa, Anna Sophie Reventlow.