Frère du réalisateur Safy Nebbou.
A neuf ans, le jeune Mehdi Nebbou part vivre avec son père près de Lyon. A partir de 13 ans, balloté d'internats en internats, régulièrement renvoyé, le jeune homme arrête les études. A 18 ans, ayant seulement un BEPC en poche, il vagabonde de petits boulots en petits boulots, et s'installe à Berlin, trois mois avant la chute du mur. De 1992 à 1994, il arpente l'Italie dans un camping car, puis retourne à Berlin et se présente à l'école de cinéma. Il y apprend la réalisation à la DFFB, l'équivalent de la Fémis à Paris.
En 1999, un étudiant de son école nommé Fillipos Tsitos prépare son premier long métrage, et lui fait passer des essais. Le film s'appelle My Sweet Home, il est choisi en Compétition au festival de Berlin en 2001.
Après ses études, Nebbou devient monteur de documentaires et joue des petits rôles à la télé allemande. En 2004, le réalisateur Samir Nasr lui offre son premier rôle principal dans Présumé coupable qui remporta le Golden Gate Award au festival de San Francisco. La même année, Benjamin Heisenberg lui propose le premier rôle de Schläfer qui remporte un succès considérable en Allemagne. Sa toute nouvelle notoriété lui permet de prendre un agent en France, qui le convainc de tenter le casting de Munich, de Steven Spielberg.
Le cinéaste retient ses essais. Pour lui, il est Ali Hassan Salameh, responsable présumé du "Septembre noir". Ce rôle lui permet de trouver un agent à Londres, qui lui ouvre des tournages anglo-américains tels Mensonges d'État de Ridley Scott. L'année suivante, il est l'un des gangsters qui font tomber Philippe Caubère dans le Truands de Frédéric Schoendoerffer. En Allemagne, son personnage de Bilal dans le téléfilm de Teresas Zimmer lui vaut un prix du Meilleur Espoir masculin 2007.
Ces diverses propositions n'empêchent pas Nebbou de tourner dans son pays natal. En 2008, il est un agent de la DGSE soupçonné de trahison dans Secret Défense avec Gérard Lanvin, incarne un truand des Liens du sang de Jacques Maillot et un arnaqueur dans Ca$h, avec Jean Dujardin. Deux ans plus tard, il est accusé de la disparition d'une jeune femme dans la campagne auvergnate de Magma.
Nebbou interprète le rôle principal du premier film d'un jeune réalisateur romain Come trovare nel modo giusto l'uomo sbagliato, puis il plonge dans un monde apocalyptique secoué par une crise pétrolière sans précédent dans le sombre Die kommenden Tage réalisé par Lars Kraume. A la fin de l'année 2010, Nebbou tourne dans Switch, le nouveau film de Frédéric Schoendoerffer, auprès d'Eric Cantona. L'année suivante, on le voit en journaliste kidnappé par les Talibans aux côtés de Diane Kruger, qu'un commando des Forces spéciales composé entre autres de Benoît Magimel vient délivrer.
En 2012, Mehdi Nebbou est à l'affiche de la comédie de Charlotte De Turckheim, Mince alors ! et en 2013, du film Cookie aux côtés de Virginie Efira et Alice Taglioni. La même année, l'acteur interprète un officier de police dans le thriller 11.6 avec François Cluzet. Il décroche ensuite l'un des rôles principaux dans l'adaptation de la bande-dessinée de Pénélope Bagieu, Joséphine. En 2016, il revient dans la suite du long-métrage intitulée Joséphine s'arrondit qui est d'ailleurs le premier film de sa partenaire à l'écran Marilou Berry en tant que réalisatrice. Deux ans plus tard, il rejoint le casting du thriller Duelles.
En plus du cinéma, Nebbou obtient des rôles dans des séries télévisées comme Engrenages, Les Témoins, Le Bureau des légendes, Homeland, Baby, Le Dernier mot et HPI. Dans cette dernière, il campe le lieutenant Adam Karadec aux côtés d'Audrey Fleurot en femme de ménage qui devient consultante pour la police.
Corentin Palanchini