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