He stepped out at the Parc des Princes stadium in Paris in the blue of France alongside his Nice teammate Moroccan-born Just Fontaine.
The midfielder was an instant success on his first appearance, assisting in the first goal in an 8–0 rout in only the second minute of the game, Mahjoub went on to play six other occasions for France including a 3–2 win over Mexico at the 1954 FIFA World Cup in Switzerland along with another Arab, Algerian Abdelaziz Bentifour.
At the age of 31, the club thought the Moroccan’s best years were behind him, and let him go but he proved all his critics wrong by guiding SO Montpellier to the 1961 French Second Division title, and promotion to the top flight.
Racing Club eventually bought back the player for a final season in 1963, before he returned to play for Wydad Casablanca, where he was later coach.
One of the greatest moments in his career came in a memorable 1962 World Cup Qualifier; when Abderrahman captained his native country Morocco against the star-studded Spain national team of Alfredo Di Stefano, Ferenc Puskás, and Francisco Gento, before stepping onto the pitch he told his teammates to look at the flags of the two nations, planted in the ground at the same height “I want you to be like these flags, on the same level as the Spaniards”.