अशी मान्यता आहे की नंदूरबारमध्ये गवळ्यांचा राजा नंद याचा दरबार भरत असे, म्हणून हे ठिकाण नंद दरबार म्हणून पूर्वीपासून प्रसिद्ध आहे. त्याचा अपभ्रंश होऊन ते नंदुरबार झाले. आजही नंदुरबार शहरास नंदभूमी म्हटले जाते. या नंदभुमीची वा नंदुरबारची ग्रामदेवता असलेल्या खोडाई मातेचे प्राचीन मंदिर हे येथील हजारो भाविकांचे श्रद्धास्थान आहे. नवरात्रीत दहा दिवस चालणारी येथील यात्रा प्रसिद्ध आहे. या यात्रेसाठी महाराष्ट्रासह गुजरात व मध्यप्रदेशातूनही भाविक येथे येतात. येथील जागृत देवी नवसाला पावते, अशी श्रद्धा असल्याने लाखो भाविक देवीच्या दर्शनासाठी येत असतात.
येथील खोडाई देवी ही राजस्थान व गुजरात येथे पुजली जाणारी खोडियार माता असल्याची मान्यता आहे. देवीची अख्यायिका अशी की सातव्या शतकात सौराष्ट प्रांतात वल्लभीपूरचे राजे शिलभद्र हे शासक होते. रोइशाळा गावातील मामनी गढवी हे राजाचे सहकारी व चांगले मित्र होते. राजाची व गढवी यांची मैत्री काही दरबारी लोकांना आवडत नसे म्हणून त्यांनी निपुत्रिक गढवीची सावली राजा व त्याच्या परिवारासाठी अशुभ असल्याचे राणीच्या डोक्यात घातले. त्यामुळे राणीने गढवी यांना दरबारात येण्यास मनाई केली. अपमानीत झालेले गढवी यांनी शंकराची प्रार्थना केल्यावर त्यांना नागलोकीच्या सात कन्या आवल, जोगल, तोगल, जानबाई, होलबाई, बीजबाई, सोसाई आणि एक मुलगा मेहरक ही अपत्ये झाली. त्यापैकी मेहरक याला एकदा विषारी सापाचा दंश झाल्यावर जानबाई पाताळलोकी अमृत आणण्यासाठी गेली. तेथून परत येताना तिचा पाय नदीतील खडकात अडकतो व त्यामुळे तिला दुखापत होते. तेव्हा ती मगरीच्या पाठीवर बसून भुलोकी येते. येताना ती लंगडत आली म्हणून तीचे नाव खोडियार माता पडले व मगर तीचे वाहन झाले.
हे देवस्थान अनादिकाळापासून स्थापित असल्याचे येथील ग्रामस्थांचे म्हणणे 
आहे. तथापि हे मंदिर सुमारे सातशे वर्षांपूर्वीचे असावे, असा अभ्यासकांचा अंदाज आहे. असे सांगितले जाते की येथील गुराखी नर्मदेच्या पलीकडे ये जा करीत असताना त्यांना गुजरात आणि राजस्थान राज्यात पुजल्या जाणाऱ्या खोडियार देवीबद्दल आस्था निर्माण झाली व आपल्या प्रांतातही या देवीचे मंदिर असावे, असा विचार करून त्यांनी या ठिकाणी खोडाई देवीची स्थापना केली असावी.
नंदूरबार शहरच्या मध्यवर्ती भागात असलेल्या या मंदिराच्या आवारभिंतीत असलेली स्वागत कमान साधीशी आहे. येथून सुमारे १५ पायऱ्या उतरून मंदिराच्या प्रांगणात प्रवेश होतो. पायऱ्यांच्या दोन्ही बाजूस कठडे आहेत. प्रांगणात प्राचीन वृक्ष आहेत व त्या वृक्षांच्या शाखांवर अनेक घंटा टांगलेल्या आहेत. खोडाई देवीच्या मंदिरासमोर यज्ञकुंड आहे. प्रांगणापेक्षा खाली असलेल्या मंदिरात येण्यासाठी तीन पायऱ्या उतरून यावे लागते. हजारो भाविकांचे श्रद्धास्थान असलेल्या या देवीचे मंदिर अत्यंत साधे व लहानसे आहे. 
भिंतीविरहित मंदिरास चार चौकोनी स्तंभ आहेत. स्तंभांवर कणी व त्यावरील तुळईवर छत आहे. मंदिरास प्रवेशद्वार सोडून चारही बाजूंनी कठडा आहे.
असे सांगितले जाते की खोडाई देवी ही रक्षक देवता असल्याने तीचा चराचरात मुक्त संचार असतो. त्यामुळेच तीचे मंदिर पूर्ण खुल्या स्वरूपाचे आहे. मंदिरात मध्यभागी खोलगट भागात देवीची स्वयंभू पाषाण मूर्ती आहे. शेंदूरचर्चित मूर्तीचे डोळे चांदीचे व डोक्यावरही चांदीचा मुकूट आहे. मूर्तीच्या बाजूला त्रिशूल व समोर परड्या आहेत. उत्सवाच्या वेळी या परड्यांमध्ये भाविक धान्य व पीठ देवीला अर्पण करतात. छतावरील षटकोनी शिखरावर आमलक व कळस आहे.
मंदिराच्या बाहेर प्रवेशद्वाराजवळ काचेच्या मखरात खोडाई देवीची संगमरवरी मूर्ती आहे. मागील वृक्षाखाली स्थानिक देवतांची शेंदूर लावलेले पाषाण आहेत. या मंदिराच्या बाजूला सन १९४३ साली बांधलेले द्वार विरहीत लहान मंदिर आहे. येथील सर्व पाषाणमूर्ती या शेंदूरचर्चित आहेत. मंदिराच्या छतावर घुमटाकार शिखर व त्यावर कळस आहे. या मंदिराच्या बाजूला वृक्षाभोवती बांधलेल्या पारावरही शेंदूर लावलेले पाषाण आहेत.
शारदीय नवरात्रौत्सव हा या मंदिरातील मुख्य वार्षिक उत्सव असतो. यादरम्यान येथे दहा दिवसांची मोठी यात्रा असते. नंदूरबार जिल्ह्यातील प्रकाशा येथील केदारेश्वर मंदिरात दर बारा वर्षांनी भरणाऱ्या यात्रेनंतर ही सर्वात मोठी यात्रा समजली जातो. या यात्रेसाठी महाराष्ट्रासह गुजरात व मध्यप्रदेश सीमेवरील अनेक भाविक येतात. या देवीच्या पूजेचा मुख्य मान आदिवासी समाजाकडे अबाधित आहे. चैत्र नवरात्री व इतर सण उत्सवही येथे साजरे होतात. दर मंगळवार, शुक्रवार, अमावस्या व पौर्णिमेला येथे देवीच्या दर्शनासाठी भाविकांची गर्दी असते.
