પૌરાણિક કથાનુસાર અંધકાસુર નામનો દૈત્ય -રાક્ષસ, તેનાં કૃત્યોથી અનીતિ તથા અત્યાચારની સીમાઓ ઓળંગી ગયો હતો. તેણે ખૂબ જ ઘમંડી સ્વરૂપ ધારણ કર્યું હતું. આ ઘમંડમાં ચકચૂર અંધકાસુર ભગવાન શિવ પર પણ આક્રમણ કરી બેઠો ત્યારે તેની સામે યુદ્ધમાં ભગવાન શિવના રુધિરમાંથી ભૈરવની ઉત્પત્તિ થઈ હોવાનું પુરાણોમાં મનાય છે. અંધકાસુરનો સંહાર કરનાર ભૈરવ શિવજીનું જ સ્વરૂપ હોવાનું મનાય છે. ભૈરવનો શાબ્દિક અર્થ - ભયાનક થાય છે. આ ભયાનક ભગવાન શિવનું દ્રસ્વરૂપ કોલસાથી પણ કાળા રંગનું છે. ભૈરવની ભૂજાઓ વિશાળ છે. સ્થૂળ શરીર છે. તેમની આંખોમાંથી અંગારા વરસે છે. તેમનાં વસ્ત્રો બિહામણા કાળા રંગનાં છે. તેમના ગળામાં દ્રાક્ષની માળા છે. હાથમાં લોખંડ જેવી ધાતુનો ભયાનક દંડ છે. શિવના આ અંધકાસુર વધના દ્રસ્વરૂપને મહાભૈરવ અર્થાત્ કાલભૈરવના નામથી પણ ઓળખવામાં આવે છે. મૃત્યુના ભયને ટાળનાર અર્થાત્ હુમલાખોરનો નાશ કરનાર મહા ભૈરવ ભારતીય દેવતાઓમાં પૂજ્ય સ્થાને છે.
શિવપુરાણમાં ભૈરવની ઉત્પત્તિ અંગે રસપ્રદ ધર્મકથા છે. માગશર માસના કૃષ્ણપક્ષની આઠમે મધ્યાહ્ને ભૈરવનું પ્રાગટ્ય થયું હતું. તેથી આ આઠમને કાલ-ભૈરવ અષ્ટમી કહે છે. કાલ ભૈરવની ઉપાસના તથા આરાધના માટે કાલાષ્ટમી વ્રતની પણ ઉજવણી થાય છે. આ આઠમની કાલભૈરવ જયંતિ તરીકે ભારત તથા નેપાળમાં ઉજવણી થાય છે. ધર્મકથાનુસાર સૃષ્ટિકર્તા બ્રહ્માએ ભગવાન શંકરની વેશભૂષા તથા તેમના ગણોના સ્વપને તિરસ્કારભાવથી વર્ણવ્યા હતા. આમ, બ્રહ્માજીએ શિવ તથા શિવના ગણોનું અપમાન કર્યું હતું. ભગવાન ભોળાનાથ શિવજીએ તો બ્રહ્માજીના અપમાન પર ધ્યાન આપ્યું નહીં. તેમ છતાં તેમના શરીરમાંથી ક્રોધથી કંપાયમાન તથા વિશાળ દંડધારી પ્રચંડ સ્વરૂપ પ્રગટ થયું. જે ભૈરવના નામથી વર્ણવાયું છે. બ્રહ્માનો સંહાર કરવા આગળ આવ્યું. બ્રહ્મા તો આ સ્વરૂપને જોઈ ચોંકી ઊઠ્યા અને ભયભીત થયા. તેઓ ભોળા શિવજી પાસે ગયા. તેમણે શિવજીને મધ્યસ્થી બનાવ્યા. શિવજીએ સૃષ્ટિકર્તા બ્રહ્માજીનું રક્ષણ કર્યું. શિવજીએ તેમના ભૈરવ સ્વરૂપ પ્રાગટ્યને શાંત પાડ્યું. દેશમાં આ શિવજી સ્વરૂપના પ્રાગટ્યને કાલભૈરવ જયંતિ તરીકે ઉજવાય છે. ભગવાન ભોળાનાથ શિવજીએ તેમના આ સ્વરૂપને - ભૈરવ કાયાને પુરી તથા કાશીના નગરપાલ બનાવ્યાનો ઉલ્લેખ પુરાણોમાં છે. સૃષ્ટિકર્તા બ્રહ્માજીના અહંકારને દૂર કરનાર - કાલ ભૈરવ આજે પણ પુરી તથા કાશીમાં જીવાત્માનો પોતાનો અહંકાર તથા અન્ય દુરાચારીઓના અહંકારને દૂર કરનાર હિન્દુ દેવતા - ભગવાન શિવરૂપે પુજાય છે. એવું મનાય છે કે શિવજીના આ સ્વરૂપે આંગળીઓના નખથી બ્રહ્માજીનાં પાંચ મુખોમાંથી એક મુખનો સંહાર કર્યો હતો. તેથી કાલભૈરવ પર બ્રહ્મહત્યાના પાપનો પણ આરોપ છે. અહીં આપણને તત્ત્વબોધ પણ મળે છે. આપણે ગમે તેટલા શક્તિશાળી હોઈએ તો પણ સામેવાળાની સાચી વૃત્તિનો સંહાર કરવાથી દોષ લાગે છે. પાંચ મુખવાળા બ્રહ્માજી સૃષ્ટિનું પાલન કરતા હતા. શિવજીના કાલભૈરવ સ્વરૂપે પોતાની શક્તિના અહંકારથી બ્રહ્માજીના પાંચમા મુખની હત્યા કરી તેથી કાલભૈરવે પણ બ્રહ્મહત્યાના આ પાપની મુક્તિ માટે ઘોર તપ કર્યું હતું. તેમણે શુભ (કાપાલિક) વ્રત કર્યું હતું.