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