प्रारंभिक इतिहास
बस्तर में काकतीय वंश के पहले नाग वंश का शासन था। बस्तर के बारे में पूरा इतिहास जानने के लिए नागवंशों के बारे में जानना जरूरी है। बस्तर में नागवंशीय शासकों की दो शाखाएं थीं इनके अपने चिन्ह थे प्रथम शाखा का चिन्ह शावक संयुक्त व्याघ्र था तो दूसरी शाखा का चिन्ह कमल-कदली पत्र था। इससे ये अनुमान लगाया जा सकता है कि प्रथम शाखा शैव मत को मानते थे तो दूसरे वैष्णव मत को मानने वाले थे। 1109 ई. का एक शिलालेख तेलुगु भाषा में मिला है। जिसमें सोमेश्वर देव और उनकी रानी का उल्लेख है।
एर्राकोट से प्राप्त एक तेलुगु शिलालेख 
(शकसंवत 945 अर्थात 1023 ई सन )से पता चलता है कि बस्तर में नागवंश के संस्थापक नृपतिभूषण थे। और इनकी राजधानी चक्रकोट (आज का चित्रकोट )थी । 1023 से 1324 तक बस्तर में नागवंशीयों ने राज किया और अपनी छाप छोड़ी ।
बस्तर के नागवंशीय शासक भोगवतीपुरवरेश्वर की उपाधि प्राप्तकर राजा बनते थे। और वे अपने आपको छिंदक कुल का कश्यप गोत्रिय मानते थे। प्रमुख शासकों का विवरण इस प्रकार है।
धारावर्ष
ये प्रथम शासक नृपतिभूषण के उत्तराधिकारी थे। इनका पूरा नाम धारावर्ष जगदेवभूषण था। इन्होंने बारसूर में एक शिवमंदिर और एक तालाब का निर्माण कराया। 1060 ई के शिलालेख से प्राप्त जानकारी के अनुसार ये उस समय के काफी प्रसिद्ध राजा थे। इसी शिलालेख में बारसूर में निर्माण कार्य की जानकारी मिलती है जिनमें तालाब और शिवमंदिर प्रमुख हैं। बारसूर का प्रसिद्ध मामाभांजा मंदिर जिसे धारावर्ष सेनापति चंद्रादित्य ने बनवाया ।
मधुरांतकदेव
धारावर्ष के बाद राजा बना । हांलाकि उसे अपने संबंधी सोमेश्वरदेव के बीच सत्ता संघर्ष हुआ। जगदलपुर से प्राप्त अभिलेख के अनुसार राजपुर ग्राम को दान में प्राप्त होना लिखा है जो एक समय में भ्रमरकोट मंण्डल के अंतर्गत था। भ्रमरकोट चित्रकोट का ही एक नाम है ।
सोमेश्वर देव
अल्पकाल में ही धारावर्ष के पुत्र सोमेश्वर दे मधुरांतक से अपना पैतृक राज्य हासिल कर लिया । सोमेश्वर देव एक महान योद्धा, विजेता और पराक्रमी राजा था। सोमेश्वर देव के 1069 से 1079 के मध्य लिखे अभिलेख से प्राप्त जानकारी के अनुसार काफी जानकारी राजा सोमेश्वर देव के बारे में मिलती है। नारायणपाल का मंदिर का निर्माण सोमश्वर देव की माँ ने करवाया था। 1111 ई में सोमेष्वर का पुत्र कन्हर देव राजा बना। इसके अतिरिक्त कुरूसपाल अभिलेख एवं राजपुर ताम्राभिलेख से भी कन्हरदेव के शासन का उल्लेख मिलता है। राजभूषण अथवा सोमेश्वर द्वितीय
कन्हर के बाद सम्भवतः राजभूषण सोमेश्वर राजा बना। राजभूषण की पत्नि गंगमहादेवी का अभिलेख बारसूर से मिला है जो शकसंवत 1130 अर्थात 1208 ई का है।
जगदेव भूषण नरसिंहदेव
सोमेश्वर द्वितीय के बाद जगदेवभूषण नरसिंहदेव राजा बना। भैरमगढ़ के एक शिलालेख से पता चलता है कि वह मणिकदेवी का भक्त था। मणिकदेवी ही दंतेश्वरी देवी है जिनका भव्य मंदिर दंतेवाड़ा में है। जतनपाल का 1118 ई. तथा 1224 ई. के अभिलेख से जगदेवभूषण नरसिंहदेव के बारे में विस्तृत जानकारी मिलती है। राजभूषण अथवा सोमेश्वर द्वितीय
कन्हर के बाद सम्भवतः राजभूषण सोमेश्वर राजा बना। राजभूषण की पत्नि गंगमहादेवी का अभिलेख बारसूर से मिला है जो शकसंवत 1130 अर्थात 1208 ई का है।
इसके बाद कोई प्रमाण नहीं हैं।
इसके बाद छिंदक नागवंश का क्रमबद्ध इतिहास नहीं मिलता है। सुनारपाल के तिथिविहीन शिलालेख से जैयसिंह नामक राजा का उल्लेख मिलता है।अंतिम लेख टेमरा से प्राप्त एक सती स्मारक लेख 1324 ई. का है। जिसमें हरिशचन्द्र नामक चक्रकोट के राजा के बारे में जिक्र किया गया है। यह सम्भवतः नागवंशी राजा ही हैै इसके बाद किवदंतियों की माने तो वारंगल के काकतीयों के हाथों नागवंशीय राजा हरिशचन्द्र पराजित हो गया। इसके बाद वारंगल नरेश अनन्मदेव ने 1324 ई. के आस-पास इन्द्रवती के उत्ती क्षेत्र को भी अपने अधिकार में ले लिया और मधोता में अपनी राजधानी बना ली इसके बाद बस्तर पर लम्बे समय तक काकतीयों का राज चला ।