Despite the legendary origin of the temple, Changu Narayan is believed to be built by Haridatta Varma, who was a Licchavi king who ruled around 325 AD several generations before Manadev I. Chronicles say that at that time Haridutta had ordered the building of four hilltop Narayan temples around the Valley. The other temples are Ichangu Narayan, at the West, Sikhara Narayan, and Lokapalasvamin. The inscription on Garuda Dhwaja, a pillar that tells of the victorious Manadev I, erected at the temple in 464 is the oldest inscription to have been discovered in Nepal. The inscription on the pillar is the first solid evidence to prove the establishment of the temple, though it indicates that the temple stood before that time. As it was the costume of the royal families to offer gifts to the temple, Changu Narayan also drew many regal worshippers. However, most of the gifts were in the form of reconstructions of the temple, which was destroyed many times by fires and earthquakes. In 607, King Amsuvarma, who highly regarded Changu Narayan, replaced the old sheath that covered the holy image and gave a large sum of money to the temple. The temple began to crumble into pieces due neglect and was left unrestored until Visva Malla (1548-1560) of Bhaktapur took up the task. Then Gangarani of Kathmandu, grandmother of Pratap Malla, repaired the temple when it was devastated by a fire. In 1694, the temple again needed reconstruction which was offered by Queen Mother Radhiklaksmi of Kathmandu. She also offered other richly gifts like a golden torana for the temple, an amount of gold and silver equal to her own weight, as well as a statue of herself and her son kneeling in front of the temple behind the Garuda Dhwaja of Manadev I. About that time the head of the image of Vishnu was offered by Bhupalendra Malla of Kathmandu when the previous one broke during a puja. Twenty years after the construction by the Queen Mother Radhiklaksmi, the temple again caught fire. This time it was Bhaskar Malla (1700-1722) of Kathmandu who rebuilt the temple and marked its completion by refinishing the roof of the temple.

In Buddhism, Changu Narayan is revered as Boddhisattva Avalokiteswara. They believe that Garuda, the mount of Lord Vishnu, and Takshaka, the king of serpents of the Kathmandu Valley, were engaged in a ferocious battle. When Garuda called upon Lord Vishnu for help, Takshaka was certain of his peril and prayed for Boddhisattva Avalokiteswara. The compassionate Avalokiteswara stopped the battle and brought peace to the adversaries. Vishnu, ashamed of his behavior in the battle offered to be Boddhisattva Avalokiteswara's steed and carried him to Changu and thus created the peculiar icon of Hari hari hari Vahan Lokeswora. At Changu Narayan, Boddhisattva Avalokiteswara is shown separately as a stone sculpture behind the temple while Garudasana Narayan, Vishnu on Garuda, is been the revered image of the temple. There are two other copies of the Garudasana Narayan image in the temple courtyard. One was made in tenth century and other in thirteenth century, which were eventually copied in many Narayan images found around Kathmandu.

The temple now covers at least seventeen hundred years of Nepalese art history. The temple, built around the third century, is decorated by some of the best samples of stone, wood, and metal craft in the Valley. In the words of one tourist guide, "When you look upon Changu Narayan, you observe the complete cultural development of the Valley."

On the struts of the two-tiered Changu Narayan Temple are the ten incarnations in which Narayan destroyed evildoers. A sixth century stone statue shows the cosmic form of Vishnu, while another statue recalls his incarnation as a dwarf when he crushed King Bali. A statue of Vishnu disemboweling Narsingha, a man-lion, is particularly interesting. The Eastern doors are made of bronze, dragons decorate the bells, and devas and griffins look out from the walls and steps. A life-sized statue of Garuda kneels before the temple. The favorite sight of many visitors is the statue of Vishnu sitting astride his steed.