इस साम्राज्य की शुरुआत सुल्तान कुली कुतब उल मुल्क ने की जो अपने चाचा अल्लाह कुली और अन्य रिश्तेदारों के साथ १६ सदी की शुरुआत में दिल्ली आ गए थे | फिर वह दक्षिण चले गए और बहमनी राजा मोहम्मद शाह की सेवा करने लगे |जल्द ही उन्होनें गोलकोंडा पर कब्ज़ा किया , क़ुतुब शाह का ख़िताब लिया और गोलकोंडा की कुतब शाही साम्राज्य की स्थापना की | १५४३ में उनके अपने बेटे जमशेद ने उनका क़त्ल कर सल्तनत की ज़िम्मेदारी संभाली | १५५० में उनकी मौत के बाद उनके छोटे बेटे ने राज किया लेकिन अफसरों ने उन्हें हटा दिया और इब्राहीम कुली को सुल्तान बना दिया |
मुहम्मद कुली कुतब शाह के शासन में हिन्दू और मुसलमानों के रिश्ते और मज़बूत हुए और कई हिन्दू कुतब शाही में उच्च पदों पर आसीन हुए जिनमें से प्रमुख थे मंत्री मदनना और अक्कान्ना | गोलकोंडा,और चार मीनार के निर्माण के बाद हैदराबाद सल्तनत की राजधानी बन गयी और दोनों ही शहरों को कुतब शाही सुल्तानों ने बसाया | इस साम्राज्य ने १७१ सालों तक गोलकोंडा पर राज्य किया और १६८७ में मुग़ल बादशाह औरंगजेब ने उनके राज्य पर कब्ज़ा कर लिया |
