The historical references to the Khandoba of Jejuri do not go back to a date earlier than the fourteenth century, According to tradition the garbhagriha of the shrine was erected by one Virpala Virmalla in 1381 A.D. Next, one comes across this shrine in the early sixteenth century. Chaitanya Prabhu, the great Vaishnav saint of Bengal had toured Maharashtra in 1510-11 A.D.During the course of his journey he visited most of the then important religious centres Vaishnavite and otherwise.
From Poona he went to Jejuri and after having visited the shrine came to know of the customs and life of the muralis. It seems he was able to persuade some of them to discontinue their practice of prostitution. But his stay was too short to uproot an evil that had clung to the social system so long. In 1635 one Ragho Mambaji from Khatav undertook the construction of the mandap and the aisles surrounding the courtyard. Large-scale building activity then seems to have been started by the middle of the eighteenth century.