Der Changu Narayan gilt als ältester noch existierender Hindu-Tempel des Kathmandutals. Man geht mittlerweile davon aus, dass die Kultstätte durch den Herrscher Haridatta Varma um das Jahr 325 im Zuge der Errichtung von vier Narayan-Tempeln an markanten Orten seines Reiches erfolgte, wobei bereits zu dieser Zeit dem Tempel auf dem Hügel von Changu eine besondere Bedeutung beigewohnt haben dürfte. Die übrigen Tempel sind der etwa 7 km nordwestlich des Zentrums von Kathmandu gelegene, in seiner heutigen Form im 18. Jahrhundert neu errichtete Ichangu Narayan, der nicht mehr existierende Lokapalasvanim, dessen Rolle heute der Shesh Narayan in der Nähe des Dakshinkali-Tempels übernommen hat, und der Bisankhu Narayan.

Das älteste schriftliche Zeugnis, welches sich im gesamten Kathmandutal erhalten hat, ist die auf das Jahr 464 datierte Sanskrit-Inschrift in der Säule Garuda Dhwaja, welche die militärischen Erfolge des Königs Manadev I. erwähnt und insbesondere herausstellt, dass der König seine Mutter vom traditionellen Sati abhielt. Neben dieser Säule befinden sich auf dem Gelände des Tempels zahlreiche weitere Statuen der Licchavi-Zeit. Der Tempel erfreute sich bis zum 8. Jahrhundert der besonderen Aufmerksamkeit der Licchavi-Könige, die umfangreiche Mittel in den Erhalt und die Erweiterung der Anlage steckten. So ließ im Jahr 607 der König Amsuvarma ein neues Gebäude zur Aufnahme des Kultbildes errichten, da Feuer und Erdbeben erhebliche Zerstörungen an der Bausubstanz des Tempelkomplexes angerichtet hatten.

Mit dem Untergang der Licchavi-Könige Mitte des 8. Jahrhunderts begann der Niedergang des Vishnuismus und der Vishnu geweihten Tempel. Erst König Vishva Malla von Bhaktapur ließ im 16. Jahrhundert den weitestgehend zerstörten Tempel sichern und Instandhaltungsarbeiten ausführen. Obwohl eher dem Shivaismus zuneigend, machten sich verschiedene Mitglieder der Malla-Dynastie in den folgenden Jahren um die Erhaltung des Changu Narayan verdient. Die den Tempel umgebende Ortschaft Champapur Mahanagar wuchs auf 700 Häuser an, ein Palast wurde errichtet und die Infrastruktur instand gesetzt.

Gangarani – die Großmutter des Königs Pratapa Malla von Kathmandu – kam Mitte des 17. Jahrhunderts für die Rekonstruktion des durch ein Feuer in Mitleidenschaft gezogenen Tempels auf. Aber bereits im Jahr 1694 mussten wiederum umfangreiche Sanierungsarbeiten vorgenommen werden, in diesem Fall finanziert von der Mutter des Königs Bhupalendra Malla von Kathmandu, Rhadiklaxmi, die auch ein goldenes Tor (torana) stiftete und eine sie und ihren Sohn darstellende Statue sowie eine große Menge Edelmetalle dem Tempel übereignete. Der König selbst ließ wenige Jahre später den Kopf des Kultbilds, der bei einer Puja zerbrochen war, erneuern. Weniger als 20 Jahre später mussten nach Zerstörungen durch Erdbeben und Feuer große Teile des Tempels erneuert werden, König Bhaskara Malla von Kathmandu versetzte das Tempelgelände 1702 dabei weitestgehend in den noch heute sichtbaren Zustand.

Im 19. Jahrhundert erfolgte die farbige Bemalung der Dachverstrebungen, die den Detailreichtum der Schnitzereien überdeckt, farblich aber mit der Gesamtkomposition harmoniert. Bis in das 20. Jahrhundert war das Betreten des Geländes für Nicht-Hindus und Nicht-Buddhisten verboten, der Indologe Sylvain Lévi musste sich bei seinem Besuch 1901 die Objekte noch vor dem Tor stehend von einem nepalesischen Assistenten beschreiben lassen.