जैसा कि नाम से ही स्पष्ट है यह ज्योतिर्लिंग मध्य प्रदेश में प्रवाहित नर्मदा नदी के बीचो-बीच स्थित है एक ओमकारेश्वर और दूसरा परमेश्वर नाम से जगत में विख्यात है। इस ज्योतिर्लिंग की कथा इस प्रकार इस प्रकार है।
एक बार देवर्षि नारद ने गोकर्ण पर्वत पर जाकर बहुत ही भक्ति भाव से भगवान शंकर की तपस्या किया। तत्पश्चात वे पर्वतराज बिन्धय के पास पहुंचे विंध्याचल ने थोड़ा अभिमान में उनकी सेवा और स्वागत किया। भरे मन से देवर्षि नारद से विंध्याचल ने पूछा हे ऋषिवर मेरे मन में किसी प्रकार की कमी तो नहीं है। कृपया आप बताइए? ऐसा कहने पर देवर्षि ने समझा की विंध्य पर्वत को अपनी श्रेष्ठता का अभिमान हो गया है। देवर्षि नारद ने बिन्धय से कहा पर्वतराज यद्यपि तुम्हें में सभी अच्छी बातें तो हैं लेकिन सुमेर पर्वत तुमसे श्रेष्ठ है क्योंकि भगवान भास्कर प्रतिदिन उसकी परिक्रमा करते हैं सुमेरू की प्रतिष्ठा देवताओं में भी है।

इतना कह कर देवर्षि नारद वहां से चले दिए लेकिन उसके बाद विंध्य अपने को धिकारता हुआ कष्ट का अनुभव करने लगा वह अपने ओंकार नामक स्थान पर विश्वेश्वर शंभु की कठोर तपस्या आरंभ कर दिया इस कठिन तपस्या से भगवान भोलेनाथ प्रसन्न होकर उसे दर्शन दिया भगवान शंकर ने विंध्याचल की तुच्छ भावना को जानते हुए यह आशीर्वाद दिया और कहा की विंध्याचल तुम जो भी चाहो उत्तम वरदान मांग लो तो विंध्याचल ने भी उत्तम वरदान की प्रार्थना की और कहा कि प्रभु आप की भक्ति मुझे मिल जाए यही हमारी कामना है। इसके बाद देवताओं और ऋषियों ने भगवान भोलेनाथ से प्रार्थना किया कि आप यही प्रतिष्ठित हो जाइए और भगवान शंकर तथास्तु कह कर वहीं प्रतिष्ठित हो गए यह दोनों ही ज्योतिर्लिंग श्रद्धालु भक्तों को भोग और योग दोनों प्रदान करने वाले हैं जो इन दोनों की पूजा अर्चना करता है उसकी जन्म मरण का चक्र बाधित नहीं करता अर्थात वह मुक्त हो जाता है।
