काली भैरव मंदिर के पास, कालियादेह का महल एक सुंदर परिदृश्य के बीच में स्थित है, जिसके दोनों ओर क्षिप्रा नदी बहती है। दूर से, यह एक टापू की तरह दिखता है। इस परिसर में बहते पानी के स्रोत और मानव निर्मित तालाब हैं। यह परिसर हरा भरा है। ये सब मिलकर इस महल को शानदार रूप देते हैं। इस महल के एक गलियारे में दो शिलालेख हैं। इन शिलालेखों में बादशाह अकबर और उनके बेटे जहांगीर के यहां आगमन की सूचना दर्ज है। महल के केंद्रीय गुंबद में दीवारों और सेंट्रल हॉल की संरचना पर शिलालेखों के साथ फ़ारसी शैली की वास्तुकला के चिह्न देखे जा सकते हैं। चूंकि पिंडारियों ने इसे पूरी तरह से ध्वस्त कर दिया था इसलिए इस महल को वर्ष 1920 में महाराजा माधवराव सिंधिया द्वारा दोबारा बनवाया गया। उज्जैन के सबसे उल्लेखनीय स्थलों में से एक इस महल का निर्माण वर्ष 1458 ईस्वी में मांडू के सुल्तान द्वारा कराया गया था। स्थानीय कहावतों के अनुसार, परिसर में एक प्राचीन सूर्य मंदिर भी था जहां बहते पानी के दो कुंड थे- सूर्य कुंड और ब्रह्म कुंड।