According to local tradition, supported by an old handwritten document preserved in the Gurdwara, one Bhag Ram, a jhivar of Lehal, waited upon ninth guru of Sikhs Guru Tegh Bahadur during his sojourn at Saifabad (now Bahadurgarh), and made the request that he might be pleased to visit and bless his village so that its inhabitants could be rid of a serious and mysterious sickness which had been their bane for a long time.
The Guru visited Lehal on Magh sudi 5, 1728 Bikram/24 January 1672 and stayed under a banyan tree by the side of a pond.The sickness in the village subsided. The site where Guru Tegh Bahadur had sat came to be known as Dukh Nivaran, literally meaning eradicator of suffering. Devotees have faith in the healing qualities of water in the sarovar attached to the shrine.
Raja Amar Singh of Patiala (1748–82) had a garden laid out on the site as a memorial which he entrusted to Nihang Sikhs. Records of a court case in 1870 mention a Guru's garden and a Nihangs' well being in existence here.In 1920, during a survey for the proposed construction of Sirhind-Patiala-Jakhal railway line, it appeared that the banyan tree under which had sat Guru Tegh Bahadur would have to be removed. But men charged with felling it refused to touch it.
Ultimately, Maharaja Bhupinder Singh ordered cancellation of the entire project. No gurudwara building had, however, been raised. It was only in 1930 that a committee was formed to collect funds and commence construction and was completed twelve years later in the year 1942. Maharaja Yadavindra Singh who was a devout Sikh built the present building and sarovar. The Gurdwara when completed passed under the administrative control of the Patiala state government. It was later transferred to the Dharam Arth Board of the Patiala and East Punjab States Union and eventually to the Shiromani Gurudwara Prabandhak Committee.