Legends of Khatu Shyamji Temple form a major part of the history of the temple. Barbareek, also known as Shayamji, was a great and brave warrior who was the son of Bhima and Nag Kanya- Ahilawati. He learned the art of fighting from his mother. Lord Shiva pleased with him three infallible arrows and Lord Agni gave him the bow which actually made him victorious in the three worlds (air, water and land). The great battle of Mahabharata was inevitable between Kauravas and Pandavas and Shayam alias Barbareek wanted to be a part of the battle having promised to be on the side of the losing side.

So when he set out for the battle field on his Blue Horse (Leela Ghora) well equipped with his bow and three arrows, he was stopped in the middle of his journey by Lord Krishna, who has disguised himself as a Brahmin, with a motive to examine the strength. Lord Krishna started to mock the boy saying he will not be able to win a big battle as this with just three arrows, to which the boy said that he had enough to create havoc in all three worlds. Lord Krishna challenged him to tie all the leaves of the peepul tree under which he was standing, with one arrow. Barbareek accepted the challenge, removed one arrow from his quiver and released it from his bow. The arrow tied all the leaves together within moments. But Lord Krishna had one leaf under his foot.

Lord Krishna knew it very well that the loss of Kauravas was inevitable and if this boy joined them then the battle will be very easily won. But when Barbareek did not relent, the Brahmin wanted charity from the boy. Shocked Barbareek wanted to know who the Brahmin was to which Lord Krishna disclosed his identity and showed him his divine form. Lord Krishna explained that according to the rule of battle a head of a brave Kshatriya needs to be sacrificed in order to worship the battlefield.

Barbareek agreed to sacrifice his head, but wanted to see the battle right till the end. His wish was granted, and so on the the12th day of Shukla Paksha of Falgun month, he gave his head to Lord Krishna (SHISH DAAN). The head was placed atop a hill near the battlefield from where Barbareek could watch the whole battle. After the battle was won by the Pandavas, the main question that needed to be answered was the main person behind the victory. So then Lord Krishna suggested Barbareek`s name saying he was the right person to judge as he witnessed the battle right through for 12 days. Barbareek`s head named Lord Krishna as the pioneering force behind the victory. His strategy, game plan and advice were very crucial for the win. Having pleased with the reply and his great sacrifice, Lord Krishna granted Barbareek with a boon that when kaliyug descends he would be worshipped by the name of Shyam in his form, and his followers would be blessed simply by taking his name.

Later his head was buried in Khatu. And one day when a cow reached that spot, milk started to flow out of her udder. So the place was dug up and the head appeared, then it was handed over to a Brahmin who worshipped it for many days. The King of Khatu, after a dream that he had, was inspired to construct a temple and the head or "SHISH" was installed on the 11th day of Shukla Pakha of Karthik month.