There are two versions of the origin of Kaitabha and his brother Madhu. The version in the Puranas said that Madhu and his brother Kaitabha were born from the earwax of Vishnu. Vishnu was ending his cosmic sleep reclined upon the serpent Sasha (also called Ananta) floating on the Milky Ocean. Brahma emerged from the lotus that grew from Vishnu’s navel. Some earwax emerged from each of Vishnu’s ears, which became the two demons known as Madhu and Kaitabha.
According to the Mahabharata version, the two demons were born from the two drops of water trapped in the lotus that came from Vishnu’s navel. Madhu had the attribute (guna) of darkness (tamas), while Kaitabha’s attribute was activity (rajas).
Kaitabha and Madhu were taught a mantra of praise to Devi (the Mother), which they used for a thousand years. Pleased, Devi appeared to them and gave them a boon. They asked to die only of their own choosing. They became bored with the world before creation, a world that was totally submerged, so they decided to cause trouble. They stole the entire Vedas and plunged into the dark waters and reached Patala (the underworld). Brahma had to waken Lord Vishnu, so he did it with praise. Vishnu agreed to retrieve the Vedas. Vishnu fought the haughty demons but was not able to win. Then he understood that they were invincible because of Devi’s boon. So Vishnu called a truce and told Kaitabha and Madhu that he was pleased with them and would grant them a boon. But they mocked Vishnu and said they did not need anything from him, as they were more powerful than he was. So Vishnu said that if that was so, then they should grant him a boon. Without any fear, they said that they would. Vishnu crafted his boon carefully, asking that they grant him the boon to kill them.
The honorable demons had to keep their promise, but they placed one stipulation on their boon: that Vishnu could not kill them in water, since everything was flooded. So Vishnu expanded himself, and the demons found themselves high and dry on Vishnu’s thigh. They enlarged themselves to be able to get their feet back into the cosmic ocean. But this time Vishnu’s expansion was so great that the demons were unable to touch the ocean. Vishnu cut off their heads with his discus. The fat that flowed from their bodies coagulated on the sea and became the earth. That was how the earth received its name as Medini (“having fatness”). They were reborn as Khara and Atikaya for more roles in later mythology.