Le comte Baudouin Ier de Flandre (IXe siècle) aurait fait construire les premières fortifications à cet endroit pour se défendre de l'invasion des vikings. Le comte Arnoul Ier de Flandre (Xe siècle) a ensuite fait renforcer la construction pour en faire réellement un château, alors en majorité composé de bois.

Le château actuel fut construit en 1180 par le comte Philippe d'Alsace. Il fut inspiré des châteaux que le comte rencontra durant la deuxième croisade. Un grand donjon en pierre de 3 étages (33 mètres de haut) fut érigé au centre de l'emplacement de l'ancien château. Le château servit de résidence pour les comtes de Flandres jusqu'au XIVe siècle, époque à laquelle il est supplanté par le Prinsenhof (aujourd'hui détruit), plus confortable et doté de grands jardins. Le château fut ensuite utilisé comme prison. Charles Quint, pourtant né au Prinsenhof, s'installa au Gravensteen lors de la répression des émeutes de 1539, pour bien affirmer que le comte venait châtier sa ville. Des maisons furent construites contre les murs et certaines de ses pierres furent même employées pour construire d'autres bâtiments. À partir de la fin du XVIIIe siècle, le château abrita une filature de coton et des ateliers, et il fut même prévu de le démolir à la fin du XIXe siècle. En 1872, le baron de Maere organisa l'opposition à cette démolition. Il constitue un des plus beaux châteaux médiévaux de Belgique.

En 1885, la ville de Gand acheta le château et lança un projet de rénovation. Les nouvelles constructions adjacentes furent enlevées et les fortifications ainsi que le donjon furent restaurés jusqu'à leur taille originelle. Les fortifications visibles actuellement ne sont donc pas totalement celles existant à l'origine.