Naya Qila was built during the rule of Sultan Abdullah Qutb Shah (1625–1672), Mughal governor of the Deccan Plateau, Aurangzeb aimed the fusillade against Golkonda Fort in January 1656. The mighty Mughal army kept up the cannon-fire but the fort stood firm. After a four-month siege, the Mughal army withdrew in April 1656. Due to heavy fusillade by the Mughals, the fort became weak and Fort walls started leaning, thus to avoid future attacks and loss Sultan Abdullah Qutb Shah ordered for the repair of fort walls and the extension of Golkonda fort, thus the construction of Naya Qila was started in the year 1656 and was completed with more additions by Sultan Abul Hasan Qutb Shah. and nearly, 30 years later when Aurangzeb become the emperor, again he set his sights on the Golkonda he completely avoided the place because the place from where he aimed the fusillade, stood the Naya Qila. A rock masonry structure with moats, it made the Golkonda all the more impregnable.[citation needed] In 1687 Aurangzeb annexed Golkonda. The fort was designed and constructed by Mustafa Khan, the royal architect of the Qutb Shahi dynasty; Makkah Masjid and Toli Masjid was designed and constructed by him.
