The Vaishnodevi cave according to geological studies is a million years old. Rig Veda does mention Trikuta but has no reference about the worship of Mother Goddess. The worship of Shakti started only in the Puranic period.

Stories behind the Vaishnodevi Temple
The first mention to the Mother Goddess is in the Mahabharata during the battle of Kurukshetra, where Arjun is said to have invoked the blessings of Mother. He calls her "Jambookatak Chityaishu Nityam Sannihitalaye" which means "you who always dwells in the temple on the slope of the mountain in Jamboo". It is also believed that the Pandavas were the first to build the temples at Kol Kandoli and Bhawan in gratitude. There are five stone structures believed to represent the five Pandavs.

The oldest historical reference is of Guru Gobind Singh, the tenth Guru of the Sikhs to visit the Holy Cave via Purmandal. The old foot track to the Holy Cave passed through this well-known pilgrimage centre. Some traditions believe this Shrine to be the holiest of all since the skull of Mata Sati fell here. Others believe her right arm had fallen here. A place called Gandarbal in Kashmir is seen in the records where the right arm of Sati is said to have fallen. Inside the holy cave there are the remains of a stone hand called Varad Hast (the hand that grants boons and blessings).

The Devis (Mother Goddesses) pooled their collective power and created a beautiful young girl. They had created her so she would live on earth and spend her time in upholding righteousness. She was ordered to be born in the house of Ratankar and his wife who resided in South India. They told her to live on earth, uphold righteousness and to evolve her spiritually - "once you have attained the level of consciousness you will merge into Vishnu and become one with him." Soon a girl was born to Ratankar, they named her Vaishnavi. The girl hungered for knowledge since an early age and nothing could satisfy her. So Vaishnavi started to look at her inner self for knowledge, through meditation and penance. She gave up all comforts and went into deep meditation. At the same time Lord Rama was in exile and visited Vaishnavi one day. Recognizing him she requested him to merge her into himself.

Lord Rama dissuaded her by saying he would visit her again after his exile, and if she could recognize him, he would fulfill her wish. He is said to have visited her but as an old man, whom she failed to recognize. Lord Rama consoled her that the time would come for to merge with the creator in Kaliyug and he would incarnate as Kalki. He directed her to meditate at the base of Trikuta hills so she could elevate herself and also bless mankind and remove their sufferings. She immediately set out and installed herself at Trikuta. Her glory spread and people flocked for her blessings.

After sometime Saint Gorakh Nath becomes curious about the incident between Lord Rama and Vaishnavi and whether she had reached the high level of spirituality. He sent his disciple Bhairon Nath and he located the ashram and started to observe her secretly. Although a Sadhvi, she carried a bow and arrows with her, and was surrounded by langoors (apes) and a ferocious looking lion. Her beauty soon enamoured him, and he began to pester Vaishnavi to marry him.

Once Vaiashnavi organized a Bhandara (Community meal) for the whole village and Gorakh Nath was invited with his followers including Bhairon. During the Bhandara, Bhairon Nath tried to grab Vaishnavi, but she decided to flee into the mountains and remain there undisturbed. But Bhairon Nath chased her.

The Goddess halted at (present day) Banganga, Charan Paduka, and Adhkwari, reached the holy cave. When Bhairon Nath continued to follow her, she beheaded him. The head fell on a distant hilltop. On his death Bhairon Nath realized his futility, he prayed to Vaishnavi to forgive him. Mata had mercy on him, so she granted him a boon that devotees of the goddess would pay obeisance after the darshan of the Goddess. Vaishnavi then shed her human form and became a rock and immersed herself in meditation forever. This rock form is 5.5 feet tall with three heads or Pindies as they are called. This is the centre of the Sanctum Sanctorum of the holy cave.