A demon named Gayasura once started to perform austerities and such were the powers of his tapasya that the demigods began to suffer. They went to Vishnu and asked him to save them. Vishnu agreed and appeared before Gayasura, asking him to cease his activities and accept a boon. “Grant me the boon that I may become the most sacred of all tirthas,” replied the daitya.

The boon was granted and Gayasura disappeared. The demigods returned to svarga, but felt that the earth seemed to be deserted now that Gayasura had disappeared. Vishnu then instructed Brahma and the other demigods to perform a sacrifice. He also asked them to go to Gayasura and ask for his body so that the sacrifice might be performed on it. Gayasura readily agreed, and as soon as he agreed, his head fell off of his body. Lord Brahma then proceeded to perform the sacrifice on Gayasura’s headless body, but as soon as the sacrifice started, the body began to shake. This meant that the sacrifice could not be properly performed and a solution had to be found. The demigods all placed a stone on Gayasura’s body so that the body would not shake, and the sacrifice could be performed. Vishnu himself also entered a stone. Because the Vishnu and the demigods are always there in Gaya, Gaya is sacred place.

Gaya was transformed into the series of rocky hills that make up the landscape of the Gaya Kshetra. Many people have flock to Gaya to perform shraddha sacrifices on his body to absolve the sins of their ancestors. Demigods and goddesses had promised to live on Gayasur's body after he died, and so the hilltop protruberances of Gaya are surmounted by various temples. These hilltop temples at Rama Shila, Preta Shila, Ram Gaya Pahar, and Brahmayoni are part of the pilgrimage circuit, and grand staircases have been built up to most of them.

Sacred places in Gaya correspond to physical features, most of which occur naturally. Ghats and temples line the banks of the sacred Phalgu River. Trees such as pipal trees and Akshayavat, the undying banyan, are especially sacred. The Mangla Gauri shrine is marked by two rounded stones that symbolize the breasts of the mythological Sati, the first wife of Shiva. The most popular temple today is Vishnupad, a place along the Phalgu River, marked by a footprint of Vishnu incised into a block of basalt, that marks the act of Vishnu subduing Gayasur by placing his foot on Gayasur's chest.