உஜ்ஜயினியை ஆண்ட விக்ரமாதித்ய மகாராஜா, காளி தேவியின் வரப்படி நீண்ட காலம் வாழ்வதற்கு, நாட்டில் ஆறு மாதம், காட்டில் ஆறு மாதம் ஆட்சி செய்ய முடிவெடுத்து அதன்படி ஆண்டு வந்தார். வன வாசம் செய்யும்போது, தனது குலதெய்வமான காளி தேவியின் சிலையை உடன் எடுத்துச் செல்வது வழக்கம். ஒரு காடாறு மாத சமயத்தில், தமிழ் நாட்டிலுள்ள மாகாளிகுடி காட்டிற்கு வந்தபோது, கொண்டு வந்த சிலையை பிரதிஷ்டை செய்து பூஜித்து வழிபட்டார். திரும்ப எடுக்கும் போது, சிலை இங்கேயே நிலை கொண்டு விட்டதால், இக் கோவிலை எழுப்பியதாக ஸ்தல வரலாறு. மற்றொரு செவி வழிக் கதையின் கூற்றுப்படி, சுபமகிடன் எனும் காளி பக்தன், சாபத்தின் காரணமாக, இரவு நேரங்களில், காளிக் கோவில் விளக்காக மாறி எரிந்துக் கொண்டிருந்தான். அவனது நண்பனான விக்ரமாதித்யன், சுபமகிடனுக்கு பதிலாக தானே சென்று விளக்காக எரிந்தான். அவனது தியாகத்தை மெச்சி பிரத்யட்சமான காளி தேவியிடம், நண்பனுக்கு சாப விமோசனம் வேண்டிப் பெற்றான். பின்னர் ஊரை விட்டுப் புறப்படும்போது, தன்னை பின் தொடர்ந்து வருமாறு காளியிடம் வேண்டுகிறான் விக்ரமாதித்யன். சம்மதித்து காளியும் பின் தொடர்ந்தாள். இவ்வூர் அருகே வரும்போது காளி வருகிறாளா இல்லையா என சந்தேகம் கொண்டு திரும்பி பார்த்தான் விக்ரமாதித்யன். அதனால் கோபம் கொண்டு இங்கேயே நின்று விடுகிறாள் காளி. காளி நின்ற இடம் என்பதால் மாகாளிகுடி என்றானதாக ஸ்தல வரலாறு.

மூலஸ்தானத்தில் மூலவராக உஜ்ஜயினி மஹா காளி அம்மன் எழுந்தருளி அருள்பாலிக்கின்றாள். பல்வேறு ஆயுதங்களை ஏந்திய அஷ்டபுஜங்கள். கீழே கிடக்கும் அசுரனை வதம் செய்யும் கோலம். மாறுபட்ட அமைப்பு உள்ள விமானம். மூலவரின் முன்பாக ஆனந்த சௌபாக்ய சுந்தரி எழுந்தருளி தரிசனம் தருகின்றார். விரித்த சடைகளுடனும் தாண்டவக் கோலத்துடனும் சுதைச்சிற்பமாக காட்சி தருகின்றார். விக்ரமாதித்தனின் பரிவாரங்களான கழுவன் மற்றும் வேதாளம் தனி சந்நிதி கொண்டுள்ளனர். சுதை சிற்ப வடிவில் முருகப்பெருமான். பூரணா புஷ்களா சஹித தர்ம சாஸ்தாவும், யானை வாகனத்துடன் விநாயகரும் ஆகிய மூர்த்தங்களை வலச்சுற்றில் தரிசிக்கலாம். கையில் கதையுடன் காணப்படும் கதாதரர் எனப்படும் ப்ரஸன்ன வெங்கடேஸ்வரர் - அலர்மேல் மங்கா சஹிதம் எழுந்தருளியுள்ளார். தவழும் சந்தான கோபால கிருஷ்ணரின் திருவுருவம் தொட்டமளூரை ஞாபகப்படுத்துகிறது. ஆஞ்சநேயரின் மூர்த்தம் அழகாக இருக்கின்றது. விலங்கு பூட்டப்பட்ட கருப்பண்ணஸ்வாமி எனப்படும் சங்கிலி கருப்பு காவல் தெய்வமாக கோவில் கொண்டுள்ளார். பொம்மியம்மாள் மற்றும் வெள்ளையம்மாள் உடனாய மதுரை வீரன், துணைவிகளுடன் நவகிரகங்கள் ஆகிய மூர்த்தங்களை தரிசிக்கலாம். கோவில் நந்தவனத்திலுள்ள ஆகாய தீர்த்தக் கரையில் சிவலிங்கத்தை தரிசிக்கலாம். சிவபெருமானின் ஜடாமுடியிலிருந்து வெளிப்பட்ட கங்கை இங்குள்ள கிணற்றில் வாசம் செய்வதாக ஐதீகம்.