La première forteresse date de 1143, quand la dynastie hindoue de Kâkâtiya régnait sur la région. Les Kâkâtîya furent suivis par l'État de Warangal, qui fut plus tard lui-même conquis par le royaume musulman de Bahmanî.

Après l'effondrement du royaume de Bahmanî, la ville devient la capitale d'un des cinq Sultanats du Deccan - Berâr, Bîjâpur, Ahmadnagar, Bîdâr et Golkonda - qui porte le même nom. En 1512, Qulî Qutb Shâh, un gouverneur turc de la province orientale de Bahmani, fonde le sultanat et la dynastie de Qutb Shahi (en) qui règne depuis Golkonda jusqu'en 1590, année durant laquelle la capitale est transférée à Hyderâbâd. Les Qutb Shâhi agrandissent le fort, dont la muraille extérieure enferme la ville dans ses 11 kilomètres, remplaçant la première construction de brique par des murs de pierre. Le sultanat durera jusqu'à la conquête du Dekkan par l'empereur moghol Aurangzeb en 1687. La forteresse résista à cette occasion à Aurangzeb pendant huit mois, ne tombant qu'à la suite d'une trahison. Après sa chute, elle n'est plus qu'un champ de ruines. Il subsiste cependant la Fath Darwâza, la « Porte de la victoire », la mosquée construite par Qulî Qutb Shâh, une armurerie et les 87 bastions, parmi d'autres structures.

Les tombeaux des sultans Qutb Shâhi, des structures gracieuses admirablement découpées et entourées par des jardins paysagers, se trouvent à environ un kilomètre au nord des murs externes de Golkonda.