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