Taha was born in 1958 in Sig (Mascara Province), Algeria, although a second source suggests he was born in the Algerian seacoast city of Oran. This town was the "birthplace of raï" music, and 1958 was a key year in the Algerian struggle for independence against French authority. He began listening to Algerian music in the 1960s, including street-style music called chaabi. Additionally, music from the Maghreb region was part of his upbringing.
He moved with his parents to France when he was ten years old, settling in an immigrant community around the French city of Lyon in 1968. His father was a textile factory worker, with long hours and low pay, such that his life was compared to that of a "modern slave", according to one account. Aged 17, Taha worked during the day at a central heating plant, described as a "menial job", and hated this work, but at night worked as a club DJ playing Arabic music, rap, salsa, funk and "anything else that took his fancy."
In the late 1970s, Taha founded the nightclub called The Rejects or, in French, Les Refoulés, where he would spin mashups of Arabic pop classics over Led Zeppelin, Bo Diddley and Kraftwerk backbeats.