Shah Abdul Majid Qureshi was born in a village in Sylhet, the eldest of three brothers and a sister. His father was forced to sell his land after spending much of his income on educating his sons, and the family lived in impoverished circumstances. To escape a life of hardship and help his family, Qureshi decided to follow the example of many of his fellow Sylhetis and try to get work on a ship with a view to migrating to America or Britain. With this in mind, he left for Calcutta in 1934. After various failed attempts, he finally managed to escape from a ship docked at Tilbury, making his way to east London where he found lodgings with other recently arrived Sylhetis.
Qureshi began his working life in Britain selling chocolates in pubs. He soon moved on to working in various Indian restaurants (including the Bengal Restaurant in Percy Street) and, in 1938, opened his first restaurant, Dilkush Delight, in Windmill Street, Soho. By 1944, he owned a different restaurant off Charlotte Street. This became known as the 'India Centre' because numerous politically active South Asians congregated there for meetings. During this period, Qureshi himself became involved in political and welfare activities concerning the South Asian community in London. He was an active member of the Hindustani Social Club and co-founder (with Ayub Ali) and President of the Indian Seamen's Welfare League. He also attended some India League meetings. A Muslim, Qureshi worshipped at the East London Mosque and helped form the London Muslim League with Abbas Ali.
Qureshi married on his first return trip to Sylhet in 1946 and eventually, in the 1970s, brought his wife and children to England where the family remained.