शास्त्रानुसार भगवान काल भैरवाचे जन्म कार्तिक महिन्याच्या कृष्णपक्षाच्या अष्टमी तिथीला झाला. या दिवशी काल भैरवाची विधिविधानाने पूजा केली जाते. काल भैरवाने ब्रह्माजींचे शिरविच्छेद केले होते. या मागील एक अतिशय रंजक कथा आहे.
तिन्ही देवांमध्ये महानतेबद्दल वितंडवाद झाला -
शिवपुराणानुसार एकदा ब्रह्मा, विष्णू आणि महेश या तिघांमध्ये वितंडवाद झाला की तिघांपैकी श्रेष्ठ कोण आहे. दरम्यान परमपिता ब्रह्मांनी भगवान शंकर यांची निंदा नालस्ती केली त्या मुळे भगवान शिव खूपच संतापले.
काल भैरवाने ब्रह्मांशी या अपमानाचा बदला घेतला -
संतापून भगवान शिव ने आपल्या रौद्र रुपेतून काल भैरवाला जन्मले. काल भैरवाने आपल्या देवांचा झालेल्या अपमानाचा बदला घेण्यासाठी आपल्या नखांनी ब्रह्मांच्या त्याच डोक्याला कापले ज्याने भगवान शिवाची निंदा केली होती. या मुळे त्यांच्या वर ब्रह्महत्येचे पाप लागले.
ब्रह्म हत्येच्या पापातून अशी मिळाली मुक्ती -
ब्रह्म हत्याच्या पापाच्या मुक्तीसाठी भगवान शिवाने काल भैरवाला प्रायश्चित करण्यासाठी सांगितले आणि म्हटले की जेव्हा ब्रह्माजींचे हे कापलेले डोकं हातातून पडेल त्याच वेळी तुला ब्रह्म हत्येच्या पापापासून मुक्ती मिळेल. शेवटी काल भैरवाचे प्रवास काशीत पूर्ण झाले आणि ते तिथेच वास्तव्यास आले आणि शहराचे कोतवाल म्हणवले गेले.