The earliest historical dynasty of Kamarupa, the Varmans (350-650), as well as Xuanzang, a 7th-century Chinese traveler ignore the Kamakhya, when it is assumed that the worship was Kirata-based beyond the brahminical ambit.The first epigraphic notice of Kamakhya is found in the 9th-century Tezpur plates of Vanamalavarmadeva of the Mlechchha dynasty. There is enough archaeological evidence of a massive 8th-9th century temple. There is a tradition that the temple was destroyed by Kalapahar, a general of Sulaiman Karrani (1566–1572), though the latest historical findings favor instead an earlier destruction during Hussein Shah’s invasion of the Kamata kingdom(1498) then under Nilambar. The ruins of the temple was said to have been discovered by Vishwasingha, the founder of the Koch dynasty, who revived worship at the site; but it was during the reign of his son, Naranarayan, that the temple reconstruction was completed in 1565. The reconstruction used material from the original temples that was lying scattered about. Banerji (1925) records that this structure was further built over by the rulers of the Ahom kingdom. Many other structures are yet later additions.
According to a legend the Koch Bihar royal family was banned by Devi herself from offering puja at the temple. In fear of this curse, to this day no descendants of that family dares to even look upward towards the Kamakhya hill while passing by.
Without the support of the Koch royal family the temple faced lot of hardship. By the end of 1658, the Ahoms under king Jayadhvaj Singha had conquered the Lower Assam and their interests in the temple grew. In the decades that followed the Ahom kings, all who were either devout Shaivite or Shakta continued to support the temple by rebuilding and renovating it.
Rudra Singha (reign 1696 to 1714) was a devout Hindu and as he grew older he decided to formally embrace the religion and become an orthodox Hindu by being initiated or taking sharan of a Guru, who would teach him the mantras and become his spiritual guide. But, he could not bear the thought of humbling himself in front of a Brahmin who is his subject. He therefore sent envoys to Bengal and summoned Krishnaram Bhattacharyya, a famous mahant of Shakta sect who lived in Malipota, near Santipur in Nadia district. The mahant was unwilling to come, but consented on being promised to be given the care of the Kamakhya temple to him. Though the king did not take sharan, he satisfied the mahant by ordering his sons and the Brahmins in his entourage to accept him as their spiritual guru.
When Rudra Singha died, his eldest son Siba Singha (reign 1714 to 1744), who became the king, gave the management of the Kamakhya temple and along with it large areas of land (Debottar land) to Mahant Krishnaram Bhattacharyya. The Mahant and his successors came to be known as Parbatiya Gosains, as they resided on top of the Nilachal hill. Many Kamakhya priests and modern Saktas of Assam are either disciples or descendants of the Parbatiya Gosains, or of the Nati and Na Gosains.