சிவன் பார்வதியை திருமணம் செய்த கதையுடன் தொடர்புடைய கோவில்களில் இதுவும் ஒன்று. சொக்கட்டான் விளையாட்டின் போது, பார்வதி சிவபெருமானின் கோபத்திற்கு ஆளானார், அதனால் அவர் அவளை பூமியில் பசுவாக பிறக்கும்படி சபித்தார். அவள் அவனிடம் மன்றாடியபோது, அவளது சகோதரன் விஷ்ணுவின் உதவியுடன் அவள் அவனுடன் மீண்டும் இணைவாள் என்று உறுதியளித்தார். எனவே, அவள் திருவாவடுதுறையில் கன்றுக்குட்டியாகப் பிறந்தாள், அருகிலுள்ள கிராமங்களைச் சுற்றி மேய்ந்து கொண்டிருந்தாள். ஒருமுறை, பசு திருக்கொழும்பியத்தில் சிவபெருமானை.

வழிபட்டது, அங்கு தன் குளம்பு லிங்கத்தின் மீது தவறுதலாக மோதி, அதன் மீது ஒரு அடையாளத்தை விட்டுச் சென்றது. தமிழில், குளம்பு “கொழுமம்” என்று அழைக்கப்படுகிறது, எனவே அந்த இடத்திற்கு அந்த பெயர் வந்தது. இங்குள்ள சிவனை கொழுமநாதர் என்றும் அழைப்பர்.

பிரம்மா நெருப்புத் தூணின் உச்சியைப் பார்த்ததைப் பற்றி பொய் சொன்ன பிறகு, அவருடைய படைப்பு சக்திகள் அவரிடமிருந்து விலக்கப்பட்டன. எனவே, பிரம்மா பல்வேறு சிவாலயங்களுக்கு தவமிருந்து யாத்திரை மேற்கொண்டார். பிரம்மா வழிபட்ட தலங்களில் இதுவும் ஒன்று. பிரம்மா இங்கு ஒரு குளத்தை உருவாக்கினார், அது இன்று கோயிலின் தீர்த்தம், பிரம்ம தீர்த்தம் என்று அழைக்கப்படுகிறது.

சாந்தன் என்ற அறிஞன் இந்திரனால் சபிக்கப்பட்டான். பறவை சாப விமோசனம் பெற இங்குள்ள சிவபெருமானை வழிபட்டதால் இங்குள்ள இறைவனுக்கு கோகிலேஸ்வரர் என்ற பெயரும், இத்தலத்தின் பழமையான பெயர்களில் ஒன்று கோகிலாபுரம் என்பதும் ஆகும்.

கௌதம முனிவரிடமிருந்து பெற்ற சாபத்தைப் போக்க இந்திரன் வழிபட்ட தலங்களில் இதுவும் ஒன்று.

இங்குள்ள மூலக் கோயில் பழங்காலத்திலிருந்தே இருந்ததாகக் கூறப்படுகிறது. 10 ஆம் நூற்றாண்டின் முற்பகுதியில் பராந்தக சோழன் காலத்தில் கட்டப்பட்டதாக நம்பப்படுகிறது, இக்கோயிலில் உள்ள பழமையான கல்வெட்டுகள், அதைத் தொடர்ந்து கந்தராதித்திய சோழன் மற்றும் செம்பியன் மாதேவி ஆகியோரால் செய்யப்பட்ட மறுசீரமைப்புகளின் சான்றுகள். அக்காலத்தில் இத்தலம் சோழ சதுர்வேதி மங்கலம் என்றும் தூய சதுர்வேதி மங்கலம் என்றும் அழைக்கப்பட்டது. முதலாம் குலோத்துங்க சோழன், விக்ரம சோழன் மற்றும் விஜயநகரப் பேரரசு – குறிப்பாக, கிருஷ்ணதேவராயர் தொடர்பான கல்வெட்டுகளும் உள்ளன. இக்கோயில் சோழர் காலத்தின் அற்புதமான, சிக்கலான கட்டிடக்கலையைக் கொண்டுள்ளது. வழக்கமான உப சன்னதிகள் தவிர, அகஸ்தியர், சட்டநாதர் மற்றும் சூரியன் உள்ளிட்ட பல தெய்வங்களுக்கான உப சந்நிதிகளும், அடிபாறைகளும் உள்ளன.