प्राचीनकाल में नर्मदा नदी ने बहुत वर्षों तक तपस्या करके ब्रह्माजी को प्रसन्न किया। प्रसन्न होकर ब्रह्माजी ने वर मांगने को कहा। नर्मदाजी ने कहा:- ’ब्रह्मा जी! यदि आप मुझ पर प्रसन्न हैं तो मुझे गंगाजी के समान कर दीजिए।’
ब्रह्माजी ने मुस्कराते हुए कहा - ’यदि कोई दूसरा देवता भगवान शिव की बराबरी कर ले, कोई दूसरा पुरुष भगवान विष्णु के समान हो जाए, कोई दूसरी नारी पार्वतीजी की समानता कर ले और कोई दूसरी नगरी काशीपुरी की बराबरी कर सके तो कोई दूसरी नदी भी गंगा के समान हो सकती है।'
ब्रह्माजी की बात सुनकर नर्मदा उनके वरदान का त्याग करके काशी चली गयीं और वहां पिलपिला तीर्थ में शिवलिंग की स्थापना करके तप करने लगीं। भगवान शंकर उनपर बहुत प्रसन्न हुए और वर मांगने के लिए कहा।
नर्मदा ने कहा - ’भगवन्! तुच्छ वर मांगने से क्या लाभ...? बस आपके चरणकमलों में मेरी भक्ति बनी रहे।'
नर्मदा की बात सुनकर भगवान शंकर बहुत प्रसन्न हो गए और बोले - ’नर्मदे! तुम्हारे तट पर जितने भी प्रस्तरखण्ड (पत्थर) हैं, वे सब मेरे वर से शिवलिंगरूप हो जाएंगे। गंगा में स्नान करने पर शीघ्र ही पाप का नाश होता है, यमुना सात दिन के स्नान से और सरस्वती तीन दिन के स्नान से सब पापों का नाश करती हैं परन्तु तुम दर्शन मात्र से सम्पूर्ण पापों का निवारण करने वाली होगी। तुमने जो नर्मदेश्वर शिवलिंग की स्थापना की है, वह पुण्य और मोक्ष देने वाला होगा।’
भगवान शंकर उसी लिंग में लीन हो गए। इतनी पवित्रता पाकर नर्मदा भी प्रसन्न हो गयीं। इसलिए कहा जाता है ‘नर्मदा का हर कंकर शिव शंकर'
