1463లో బీదర్ కి చెందిన రెండో సుల్తాన్ మహమ్మద్ షా బహమనీ హైదరాబాద్ ప్రాంతానికి సుబేదార్ గా సుల్తాన్ కులీ కుతుబ్ ఉల్ ముల్క్ ని పంపించారు. బహమనీ రాజ్యం 1518లో విచ్చిన్నమైన తరువాత సుల్తాన్ కులీ తనకి తాను స్వాతంత్య్రం ప్రకటించుకుని, సుల్తాన్ కులీ కుతుబ్ షా అని తన కొత్త పేరును ప్రకటించారు. గోల్కొండలో కాకతీయుల కోటలో తన రాజధాని ఏర్పాటు చేసుకుని కుతుబ్ షాహీ వంశాన్ని స్థాపించారు.
1589లో అయిదవ పాలకుడు మొహమ్మద్ కులీ కుతుబ్ షా రాజధానిని మూసీ నదీ తీరాన ప్రస్తుత హైదరాబాద్ కి మార్చారు. హైదరాబాద్ అనే పేరు ఎలా వచ్చింది అనే దానిపై మనకి తెలిసిన కొన్ని కథనాలు ఉన్నాయి. అందులో ప్రత్యేకంగా చెప్పుకోదగ్గవి రెండు - మొహమ్మద్ కులీ కుతుబ్ షా కొడుకు హైదర్ పేరు పెట్టారు అన్నది ఒక కథ కాగా, హైదర్ మహల్ అన్న బిరుదు పొందిన రాజనర్తకి అయిన భాగమతి అనే మహిళ పేరు పెట్టారని కొంత మంది చెప్తారు.
