Bentaleb made his senior international debut in March 2014 and has represented Algeria at the 2014 FIFA World Cup and the 2015 Africa Cup of Nations. As of November 2016, he has won 21 international caps and scored 4 goals.
Born in Lille to Algerian parents, Bentaleb started his career at the academy of local side, Lille. However, he was released from the academy at the age of 15 and then went to Belgium to play for Mouscron. Bentaleb then went on trial with Birmingham City before eventually signing into the academy of Tottenham Hotspur in January 2012. During the 2012–13 season Bentaleb broke into the under-21 side at Tottenham and scored four goals in fourteen matches, including a winning goal against Arsenal's Academy. His performance that season earned him a new four-year contract at Tottenham Hotspur until 2018.
On 22 December 2013, Bentaleb was selected into the 18-man first-team squad for Tottenham Hotspur in a Premier League match against Southampton. He made his professional debut in that match when he came on as a sub in the 50th minute for Mousa Dembélé, Tottenham won the match 3–2. His first start for Spurs came in the North London derby against Arsenal in the third round of the FA Cup on 4 January. Bentaleb scored his first goal for the club on 17 December 2014 in the fifth round of the Football League Cup against Newcastle United.
On 1 March 2015, Bentaleb started for Tottenham in the 2015 Football League Cup Final, a match they lost 2–0 to Chelsea. On 6 July, he signed a new five-year contract, which runs until 2020.
On 25 August 2016, Bentaleb joined Bundesliga side Schalke 04 on a season-long loan deal. He went on to make his debut in an away match against Frankfurt on 27 August 2016, which Schalke lost 1-0. His first start came the next weekend against Bayern, after which Bentaleb became a fixture in new manager Markus Weinzierl's starting eleven. Enduring Schalke's worst ever start to a Bundesliga with five consecutive losses, Bentaleb confirmed his desire to remain in Gelsenkirchen, saying that "at Schalke they believe in me", while also appreciating the fans' ability to stick beside a team going through a rough patch in comparison to English fans. On 15 October, Bentaleb came through with his first goal for Schalke, a strike from distance that put Schalke temporarily ahead of Augsburg in a 1–1 draw. This was the first goal reviewed by goal-line technology in the Bundesliga to be successfully allowed. In Schalke's next match, Bentaleb followed that performance up by scoring two goals against Mainz in a 3–0 victory, becoming the first Algerian to achieve the feat in Bundesliga play. Immediately after the match, a report emerged claiming that Bentaleb had already signed a four-year contract to remain with Schalke, which would go in effect after a permanent buying option in his loan deal was picked up, putting his future at White Hart Lane in question.
On 24 February 2017, Tottenham Hotspur announced that they have reached an agreement with Schalke 04 for Bentaleb transfer to be made permanent at the end of loan period.
On 14 November 2012, Bentaleb made his debut for France U19 in a friendly match, coming on as a half time substitute in a 3–0 loss to Germany U19.
Despite having represented France, he has been courted by the Algerian Football Federation, and some sources said he already accepted. In January 2014, Tottenham Hotspur manager Tim Sherwood suggested that The English Football Association were also interested. However, Bentaleb would not meet the requirements to play for England under the unique rules set out in the Home Nations agreement. The Home Nations agreement requires that players engage in a minimum of five years of education before the age of 18 within the territory of the relevant association and do not offer national team eligibility through residency.
On 15 February 2014, Bentaleb pledged his international future to Algeria. A few days later, he was called up by Algeria coach Vahid Halilhodžić for a friendly match against Slovenia. He made his debut on 5 March, playing the full game in a 2–0 win over Slovenia. He scored his first goal for his country against Romania on 4 June 2014 at the Stade de Genève in Switzerland.
In June 2014, Bentaleb was named in Algeria's 23-man squad for the 2014 FIFA World Cup. He started in midfield for the team's opening match of the tournament – a 2–1 defeat by Belgium in Belo Horizonte on 17 June. He also played the full ninety minutes for Les Fennecs in their two other Group H matches; a 4–2 defeat of South Korea and a 1–1 draw with Russia. However, he was an unused substitute during the team's 2–1 defeat to Germany in the round of 16.
On 15 December 2014, Bentaleb was named in Algeria's 23-man squad for the 2015 Africa Cup of Nations in Equatorial Guinea.As of match played 28 August 2017.
As of match played 7 January 2017.
Scores and results list Algeria's goal tally first.
Tottenham HotspurFootball League Cup Runner-up: 2015
Bundesliga Rookie Award by TAG Heuer the first leg :best young player 2016-2017
Bundesliga Goal of the Season: 2016-2017 vs FC Augsburg on Matchday 7