Non si conosce molto della storia antica di Visby, ma è certo che intorno al 900 essa fosse un centro di commerci.

Nel corso del XII secolo venne eretta la Cattedrale di Visby, dedicata a Santa Maria e modificata nel XIII secolo. Nei secoli successivi vennero costruite molte altre chiese, mentre la città fioriva grazie alla sua partecipazione alla Lega anseatica.

Agli inizi del XIII secolo si iniziò a dotare Visby di una cinta muraria difensiva, ricostruita intorno al 1280 nella forma che vediamo ancor oggi (anche se alcune delle torri che la contraddistinguono non furono costruite fino al XV secolo). Le mura, quasi completamente intatte, sono alte 11 metri e lunghe 3,4 chilometri.

Nel 1361 l'isola di Gotland venne conquistata da Valdemaro Atterdag, rendendo Visby una città danese. Nel 1391, 1394 e 1398 venne attaccata e saccheggiata dalla Fratellanza Vitaliana, un gruppo di pirati del Mar Baltico.

Nel 1411 Eric di Pomerania si fece costruire il castello di Visborg, una fortezza che si trova nei pressi della città, e vi si stabilì per dodici anni, periodo nel quale Visby divenne virtualmente un covo di pirati e il commercio si fermò. Nel 1470 la città fu infatti espulsa dalla Lega anseatica.

Nel 1525 avvenne il fatto più disastroso della storia della città: i mercanti di Visby erano in lite con Lubecca, il che ebbe come conseguenza che un gruppo di tedeschi cominciò a bruciare tutte le chiese della città svedese ad eccezione della cattedrale. Le rovine delle chiese sono state conservate fino ad oggi, il che contribuisce a dare uno charme unico alla moderna Visby.

Dopo 300 anni di occupazione danese, con il Trattato di Brömsebro del 1645 l'isola di Gotland tornò sotto il controllo dell'impero svedese. Poco venne fatto per sviluppare l'economia dell'isola, compreso un timido tentativo del XVIII secolo che non portò a grandi risultati. Solo agli inizi del XIX secolo Visby ricominciò ad attrarre i commerci ed un'industria portuale di una certa importanza.