Nato e cresciuto a Parigi, ha un fratello di nome Mikaël, anch'egli attore.[1] Debutta come attore nel 1998 interpretando il ruolo di Benjamin nella soap opera Saint Tropez, in onda su TF1. Dopo essere uscito dal cast della soap opera nel 2001, Fitoussi prende parte a numerose produzioni televisive, nel 2006 recita nella miniserie televisiva L'état de Grace, dove interpreta il ruolo di Dan Odelman, ginecologo del Presidente della Repubblica interpretata da Anne Consigny. Sempre nel 2006 prende parte al film per la televisive L'avvelenatrice, incentrato sul caso di Marie Besnard.
Fitoussi diventa noto grazie al ruolo del giovane procuratore Pierre Clément nella serie televisiva Spiral.
Nel 2013 ottiene un piccolo ruolo di un pilota nel film World War Z. Successivamente inizia ad ottenere ruoli in produzioni fuori dalla Francia, ha interpretato il ruolo di Henri Leclair nelle prime tre stagioni della serie televisiva britannica Mr Selfridge e ha lavorato nelle serie televisiva statunitense American Odyssey, cancellata dopo una sola stagione.