The earliest records that speak about the existence and popularity of the Narayan Cult in Orissa during the 5th-6th century of the Christian era were issued by the Mathara dynasty, who began to rule after Maharaja Samudragupta’s southern expedition. The Guptas were follower of Vaishnavism and they helped advance the popularity of Vaishnavism in Orissa.
In the Ningondi plates of Prabhanjan, Varman the King declares himself Bhagavata Svami Narayana Padanudhyatah. This grant records mention of the bright fortnight of Karttika. It indicates that the King was a follower of Vaishnavism and he granted the land after performing the Karttika-Ekadasi Vrata.
Another ruler of the same family, Ananta Saktivarman, used the title Narayana Svaminah Padabhaktah Paramadaivata in his Andhavaram Plates.  Different Vaishnavite epithets, like ‘Paramabhagavata’, came to be used by the members of the Pitribhaktah family, including Chandavarman  and Nandaprabhanjan Varman.  The records of the Matharas give a clear indication to the existence and popularity of the Narayan Cult, which was patronised by the ruling house of Kalinga during the 5th-6th century A.D.
The fall of the Mathara and Pitribhaktah dynasties was a serious setback for the worship of the Narayan cult. But in the 7th century A.D., the earliest king of Sailodhava of Kongada was named Madhavaraja. In his inscriptions he was called Chakradhara and Madhava. An image assignable to the 7th century A.D., now preserved in the Orissa State Museum, depicts the scene of Kaliyadamana, and a few images of Madhava are found from the Prachi Valley.
A Sirpur stone inscription issued by the queen mother Vasta constructed the famous brick temple known as Lakshman temple in Sirpur  belonging to the 8th century A.D. The inscription opens with the salutation to Purushottama (Vishnu) and also invokes Purushottama as Nrsimha. Thus it seems that Vishnu in the form of Lord Narasimha gained popularity at that time.
The Bhaumakaras of Utkal (8th century A.D.) crushed the Sailodbhavas and invaded Tosala and Kongada. The first group of Bhaumakara kings were all Buddhists. But at that time a great Hindu Philosopher, Sankaracharya, who was a philosopher of “Non-Dualism” oR Advaita-vada, visited several placeS to propagate Hindu religion and culture. He established a Govardhana Matha at Purushottamakshetra (Puri).  This influenced the Bhaumakara Kings and towards the 9th century A.D., the Bhaumakara Kings adopted Saivism and the queens had accepted Bhagavatism. Tribhuvana Mahadevi in her Dhenkanal plate  and the Baud plate declares herself as a Paramavaisnavi, the devout worshipper of Visnu, and Paramabhattarika Maharajadhiraja Paramesvari.
In the Talcher Plate  of Sivakaradeva, King Gayada is said to have the glory similar to that of Vaikuntha. In the Bhaumakara copper plate we come across several Vaishnavite names like Hari, Damodara, Haladhara, Madhusudana, Mahidhara, Trivikrama, Govinda, Govardhana, Janarddana, Purushottama, Sudarsana, Balabhadra, Vamana, Vasudeva, Visnu, Narayana, Narasimha, Padmanabha, etc. Thus the period of Bhaumakaras is important for Orissa from the religious points of view. For the first time we come across the names of Purushottama and Balabhadra in the inscriptions of Utkala.
The Somavamsis of Daksina (South) Kosala were all devout worshippers of Siva, but they give equal respect for other Brahmanical religious faiths. King Madhavagupta Yayati in his Narsimhapura Plates  described him as the representative of Madhusudana, Visnu. One Visnu temple built by the Panduvamsi of Daksina or South Kosala has a representation of Visnu Anantasayi in the centre of the door linel.
Towards the 12th century A.D. under Anantavarman Chodagangadeva, Puri became an important centre of Vaishnavism. Though Chodagangadeva was a follower of Saivism he later he accepted Bhagavatism. For the first time in the Korni Plates , dated saka year 1034 (1112 A.D.), he adopted titles like Parama Mahesvara, Paramavaisnava and Paramabrahmanya.
The religious life in Orissa has been dominated by the Cult of Purushottama Jagannath even since the famous Puri temple was built in the 12th century A.D. by Ananta Varman Chodagangadeva (1078-1174 A.D.).  The First epigraphic evidence to the construction of Jagannath temple by the powerful Ganga Monarch Chodagangadeva is found in the Dasgoba copper plate  grant of his grandson Rajaraja Deva III. But the temple chronicle states that the temple was built by Yayatikesari (13 Anka according to the first Panji; 59th Anka according to the 2nd Panji).  Thus it is a matter of controversy to know the remnant of the first Purushottama temple of Puri.
Chodagangadeva died in 1146 A.D., but the Jagannath temple work was not completed during his lifetime. It was finished under Anangabhimadeva III (1212-1239 A.D.) and the consecration ceremony accomplished in 1230 A.D. The Deities were removed from the Nrsimha temple to Srimandira. Its presiding Deity was Jagannath, Lord of the Universe King of the Kingdom of Orissa.  The Ganga family accepted Jagannath as their family deity and real ruler of the land. Anangabhima Deva III, in the Draksharama inscription (1216 A.D.) declared himself as rauta, deputy and putra, son of Purushottama, Rudra and Durga. 
After the death of Anantavarman Chodagangadeva, his wife Kasturikamodini built the temple for Jagannath in Tekkali . Maharaja Anangabhimadeva III was succeeded by his son Narasinhadeva I (1238- 39 A.D.). He constructed a beautiful sun temple at Konark. His sister, Chandrika Devi, constructed Anantavasudeva temple on the bank of Bindusarovara at Bhubaneswar. In the context of such analysis it can be said that the Narayan cult in Orissa took on important form with the construction of the Jagannath temple at Puri, and the worship of Narayana continued under the Gajapati dynasty.