Fils d'un journaliste juif, Radu Mihaileanu quitte la Roumanie en 1980 durant la dictature de Ceaușescu pour se réfugier en Israël, puis en France où il étudie le cinéma à l'Idhec (ancien nom de la Fémis). Après ses études, il exerce le métier d'assistant réalisateur durant les années 1980, notamment auprès de Marco Ferreri avec qui il collabore ensuite à l'adaptation du dialogue de Platon pour le téléfilm Le Banquet en 1989.
Il a publié un recueil de poèmes en 1987, intitulé Une vague en mal de mer.
En 1993 sort Trahir, son premier long métrage en tant que réalisateur, dont il coécrit le scénario. Le film bénéficie d'un bon accueil critique et obtient plusieurs prix dans des festivals (Montréal, Istanbul…). Après la réalisation d'un premier téléfilm en 1997 pour M6 (Bonjour Antoine), Radu Mihaileanu signe son deuxième long métrage, Train de vie. Le film obtient un succès international, notamment grâce à deux prix gagnés durant le Festival de Venise en 1998. Alors qu'un projet de film noir tourné en anglais n'aboutit pas, Mihaileanu accepte de tourner un autre téléfilm, Les Pygmées de Carlo, pour Arte, en 2002.
Après une rencontre avec des immigrés éthiopiens en Israël, il se lance dans une vaste entreprise qui aboutira en 2005 à Va, vis et deviens, qui le consacrera César du meilleur scénario original l'année suivante, après également des prix glanés durant la Berlinale 2005.
En 2009 sort Le Concert qui attire près de 1,9 million de spectateurs en salles. Le film raconte la tentative d'un groupe d'anciens musiciens exclus du Bolchoï de Moscou de remplacer secrètement leurs successeurs actuels pour interpréter un concert au théâtre du Châtelet à Paris.
En 2011, changeant encore radicalement de sujet et d'environnement, Radu Mihaileanu sort La Source des femmes, avec Leïla Bekhti et Hafsia Herzi, film dans lequel les femmes d'un village du Maghreb revendiquent l'égalité avec leurs maris en refusant d'accomplir toutes les tâches non partagées. Le film est en sélection officielle au festival de Cannes 2011.