As per the history the temple existed from ancient time and there are two different stories about the existence of the deity.
In one of the stories, Madayikavu Amma who is in the form of Bhadrakali originally was existing in Shiva Kshethara Thiliparambha Rajarajeshwara temple. But, as she was non- vegetarian and could not continue to exist at Thiliparambha Rajarajeshwara temple, she ordered the then King of that region to construct a separate temple in her name. Then ‘Madayikavu’ temple came into existence as per the deity’s wish.
In another ancient story it is believed the people of Madayi were troubled by a demon named ‘Dharaka’ and Madayikavu Amma in the form of Kali killed him and requested Lord Shiva to give a place on earth where people can worship her always. Lord Shiva ordered his disciple Parashuram and as per his orders Parashuram hit the ground with his sword and the sea which made way for a hill was transformed into a “Punya Kshethara’ of mother Kali very popularly known as Madayi Kavu Ammaor Thiruvar Kadu Bhagavathi.