Mehdi Nebbou est né dans le Pays basque français d'une mère allemande et d'un père algérien. Il part s'installer à Berlin à l'âge de dix-huit ans. Après divers petits boulots en Allemagne et en Italie où il apprend le métier de menuisier, il se présente à l'examen d'entrée de l'Académie du Cinéma de Berlin, la Deutschen Film- und Fernsehakademie. Il y étudie la réalisation pendant 5 ans.
Alors qu'il aide un autre étudiant de l'Académie du Cinéma de Berlin pour son casting, il rencontre le réalisateur Filipos Tsitos qui lui propose de faire des essais pour l'un des rôles principaux de son film. C'est ainsi qu'il fait ses premiers pas en tant qu'acteur de cinéma. Le film My sweet home fut en 2001 le seul film allemand en Compétition au Festival de Berlin.
En 2004 le réalisateur Samir Nasr lui offre son premier rôle principal dans Présumé coupable (Seeds of doubt) qui gagnera le prix du Meilleur Film, le Golden Gate Awards, au Festival du film de San Francisco. En 2005, sa carrière prend un tournant considérable en Allemagne grâce au film Schläfer de Benjamin Heisenberg qui est encensé par la critique et considéré comme l'un des films pionniers de la "Nouvelle-Vague allemande". Le film a sa Première à Cannes en Sélection officielle au Festival de Cannes 2005 : section Un Certain Regard. Steven Spielberg le prend dans Munich pour interpréter Ali Hassan Salameh, le cerveau présumé du Septembre noir. La même année il interprète un Imam dans le film d'Hal Hartley intitulé Fay Grim, aux côtés de Jeff Goldblum. C'est alors qu'il décide de rentrer en France. Son premier rôle important dans un film français est celui du gangster laconique Hicham dans le film Truands de Frédéric Schoendoerffer, où il joue aux côtés de Béatrice Dalle, de Benoît Magimel, d'Olivier Marchal et de Philippe Caubère.
C'est alors que le réalisateur Jacques Maillot qui lui offre le personnage de José Lazaga dans Les Liens du sang aux côtés de Guillaume Canet et de François Cluzet. C'est en 2007, grâce au film Teresas Zimmer de Constanze Knoche, qu'il reçoit le Prix du meilleur espoir masculin en Allemagne, First steps Schauspielpreis 2007. Ensuite viendra la comédie Ca$h d'Eric Besnard, aux côtés de Jean Reno, de Jean Dujardin et de Valeria Golino. Dans la série Engrenages produit par la BBC et Canal+, il interprète Mustapha Larbi, un parrain de la mafia parisienne vers lequel toutes les pistes vont conduire. Dans Secret Défense de Philippe Haïm il est un agent des services secrets français accusé, à tort, de conspiration contre l'Etat; aux côtés de Gérard Lanvin, Nicolas Duvauchelle, Simon Abkarian et Rachida Brakni. Dans le film de Ridley Scott, Mensonges d'état, il interprète un ancien espion qui, tombé dans les mains de réseaux terroristes, tente une dernière fois de retrouver une vie normale, aux côtés de Leonardo Dicaprio et de Russell Crowe.
