Sehrai was born in 1944 in Tekipora village of Lolab Valley in Kupwara district of Jammu and Kashmir to Shams-ud-din Khan. His ancestors had migrated from areas now part of modern-day Pakistan to Kashmir. He also has two elder brothers. One of them is Muhammad Yousuf Khan, founder of Tehreek-e-Islami, who died in 2016. The other is Qamar-ud-din. As a student, he used to show an interest in religious and political discussions. He also has an interest in poems and literature and also authored writings as well as poems, most of which were published in "Azaan" and "Tulu" magazines. He started publishing Tulu in 1969 from Sopore. Sehrai commissioned articles, took care of its design as well as printing and also wrote for the column called Safa-e-Paksitan which covered the events happening in Pakistan. He and Syed Ali Shah Geelani dedicated a special issue to Allama Iqbal in which they both wrote lengthy columns against Kashmiri socialists and a writer called Ashia Bhat while also defending the magazine and Jamaat-e-Islami, after the magazine's claim of Iqbal not being a socialist led to a controversy. He is the father of four children, which includes three sons and a daughter. His youngest son Junaid Ashraf Khan became a militant in March 2018, joining Hizbul Mujahideen. Jammu and Kashmir Police's inspector-general for Kashmir Division S.P. Pani has stated that that another of Sehrai's sons is named Rashid Ashraf. Per a media report, two of his sons according to Ministry of Home Affairs sources are named Khalid and Abid Ashraf. Sehrai has stated that he never expected Junaid to become a militant, but won't request him to return. Junaid later became Hizbul's divisional commander, but was killed in an encounter with the CRPF and J&K Police on 19 May 2020. Sehrai personally led his funeral prayers attended by about 300 people despite the lockdown due to the coronavirus pandemic.
Sehrai became an affiliate of Syed Ali Shah Geelani in 1959 after being encouraged to do so by his elder brother. He has stated that he officially became a member as a "rukun" of Jamaat-e-Islami in 1960. Sehrai was jailed for the first time in 1965 over anti-government activities after he delivered a speech criticising Ghulam Mohammed Sadiq's government for repression of free speech and arrest of members of the Moh-e-Muqaddas Majlis-e-Amal. After he started focusing on the Tulu magazine, JeI cadres complained about him staying away from the organization's activities and the magazine was thus shut down in 1971. After the JeI expelled Geelani following the formation of his own Hurriyat Conference party due to opposition to a dialogue with the central Indian government, Sehrai also left the group and was appointed as Tehreek-e-Hurriyat's general secretary in 2004 during its foundation. Following the 2016-17 Kashmir unrest, National Investigation Agency published a report to address his involvement in issuing protest calanders and carrying out anti-India activities. He was appointed as the acting chairman by Tehreek-e-Hurriyat's Majlis-e-Shoora on 19 March 2018. Later, he was elected as the chairman for 3 years on 19 August by a margin of 410 votes out of a total of 433, in the first-ever Hurriyat election since Geelani stepped down.
