The Puranas mention the region of Vadvali as a place visited by Rama and Parashurama, avatars of the god Vishnu. The legend says that Parashurama performed a yajna at Vadvali and the hills of volcanic ash in the area are its residue.
Thousands of years ago, a Rakshasa named Kalikut troubled the rishis and humans in the region of Vadvali and waged a war against the devas. Distressed, the gods and sages headed by Vashishta performed the TriChandi yagna, a fire offering to the Goddess, to please Her. An aahuti was not granted to Indra. Enraged, Indra hurled his Vajra – one of the most powerful weapons in Hindu mythology- at the yajna. The terrified gods and sages prayed to the Goddess to save them. The Goddess appeared in all her glory at the site and not only swallowed the Vajra and humbled Indra but also killed the demons. Rama requested that the Goddess stay in the region of Vadvali and be known as Vajreshwari. Thus, the Vajreshwari temple was established in this region.
Another legend says that Indra and other devas went to goddess Parvati and requested her to help slay demon Kalikala. Goddess Parvati assured them that she would come to their aid at the right time, and ordered them to fight with the demon. In the battle, Kalikala swallowed or broke all weapons thrown at him. Finally, Indra threw the Vajra at the demon, which Kalikala broke into pieces. From the Vajra emerged the Goddess, who destroyed the demon. The devas extolled her as Vajreshwari and built her temple.
The original temple of Vajreshwari was at Gunj, five miles (8 km) north of Vadavli. It was moved to Vadvali after its destruction by the Portuguese.
In 1739, Chimaji Appa – the younger brother and military commander of Peshwa Baji Rao I – had set up camp in the Vadvali region on his way to capture the Portuguese-held Bassein Fort of Vasai. The fort was unconquerable even after a three-year war. Chimaji Appa prayed to goddess Vajreshwari that if he could conquer the fort and defeat the Portuguese, he would build a temple to her. According to legend, the goddess Vajreshwari appeared in his dream and told him how to conquer the fort. On 16 May, the fort fell and the defeat of the Portuguese in Vasai was complete. To celebrate his victory and to fulfill the vow taken in front of the goddess Vajreshwari, Chimnaji Appa ordered the new Subhedar, Shankar Keshav Phadke, to build the Vajreshwari temple.