उज्जैन के काल भैरव मंदिर को राजा भद्रसेन ने बनवाया था, जिसका जिक्र स्कन्द पुराण के अवन्ती खंड में भी किया गया है। परमार शासनकाल (9वीं से 13वीं शताब्दी) के दौरान की शिवजी, माँ पार्वती, भगवान विष्णु और गणेश जी की प्रतिमाएं इसी जगह से मिली है। वहीं राजा भोज के समय इस मंदिर का पुनर्निर्माण भी करवाया गया था।

उज्जैन के राजा महाकाल ने ही कालभैरव को शहर की रक्षा के लिए नियुक्त किया है। इसी वजह से कालभैरव को शहर का कोतवाल भी कहा जाता है। भैरव बाबा के इस मंदिर में उनको मदिरा चढ़ाई जाती है, लेकिन मदिरा जाती कहां है ये रहस्य आज रहस्य बनके ही रह गया है। कालभैरव की इस प्रतिमा को मदिरा पीते हुए देखने के लिए यहां हजारों श्रद्धालु हर रोज पहुंचते हैं। इस मंदिर में भगवान कालभैरव की प्रतिमा सिंधिया पगड़ी पहने हुए दिखाई देती है। यह पगड़ी बाबा भैरवनाथ के लिए ग्वालियर के सिंधिया परिवार की ओर से आती है। यह प्रथा सैकड़ों वर्षों से चली आ रही है।

उज्जैन के काल भैरव मंदिर का निर्माण मराठा स्थापत्य शैली के अनुसार किया है, मंदिर की दीवारों में मालवा शैली में बने शानदार चित्रों के अवशेष अभी भी देखने को मिलते हैं। वहीं मंदिर के गर्भ गृह में भगवान काल भैरव की मूर्ति एक चट्टान के रूप में विराजमान है।

उज्जैन के इस कालभैरव बाबा को मदिरा का भोग लगाया जाता है। इसके अलावा भक्त यहाँ पर मावे और बेसन के लड्डू का भी भोग लगाते हैं।