बताया जाता है कि यह विश्व का इकलौता मंदिर है, जहां खंडित शिवलिंग की पूजा होती है। इस मंदिर के बारे में जानकारी पदम पुराण के पाताल खंड में भी मिलता है। पौराणिक कथाओं के अनुसार, त्रेतायुग में यहां पर राजा वीर सिंह का राज हुआ करता था। उस वक्त इस नगर का नाम देवपुर था, जिस अब बिरसिंहपुर नाम से जाना जाता है। बताया जाता है कि राजा वीर सिंह भगवान महाकाल ( mahakal ) को जल चढ़ाने के लिए घोड़े से उज्जैन जाते थे। यह सिलसिला वर्षो तक चलता रहा। उम्र अधिक होने के कारण राजा को उज्जैन जाने में परेशानी होने लगी। कहा जाता है कि एक दिन भगवान महाकाल ने स्वप्न में राजा को दर्शन दिए और देवपुर में ही दर्शन देने की बात कही।
कुछ दिन बाद देवपुर में गैवी यादव नामक व्यक्ति के घर के चूल्हे से रात को शिवलिंग रूप निकलता, जिसे गैवी यादव की मां मूसल से ठोक कर अंदर कर देती। कई दिनों तक शिवलिंग बाहर निकलता और गैवी यादव की मां मूसल से ठोक कर अंदर कर देती। इसके बाद महाकाल ने एक बार फिर राजा को स्वप्न में दर्शन दिये।
महाकाल ने राजा से कहा कि मैं तुम्हारे नगर में निकलना चाहता हूं, लेकिन गैवी यादव की मां निकलने नहीं दे रही है। इसके बाद राजा ने गैवी यादव बुलाया और स्वप्न की बात बताई। उसके बाद उस जगह को खाली कराया गया, जहां से शिवलिंग निकला। इसके बाद राजा ने यहां भव्य मंदिर का निर्माण कराया। साथ ही महाकाल के कहने पर ही शिवलिंग का नाम गैवीनाथ रख दिया। तब से ही भोलेनाथ को गैवीनाथ के नाम से जाना जाता है।
बताया जाता है कि जो व्यक्ति महाकाल के दर्शन करने के लिए उज्जैन नहीं जा सकता, वह बिरसिंहपुर के गैवीनाथ का दर्शन कर ले तो पुण्य उतना ही मिलता है। वैस तो यहां हर दिन हजारों की संख्या में श्रद्धालु पहुंचते हैं लेकिन सावन ( Sawan 2019 ) के महीने की बात ही अलग है। लोग कहते हैं कि चारोधाम करने से जितना पुण्य मिलता है, उससे कहीं ज्यादा गैवीनाथ पर जल चढ़ाने से मिलता है।
