Fitoussis Eltern sind sephardische Juden, die als französische Bürger in Algerien geboren waren, aber nach dem Algerienkrieg im Teenageralter von dort als Pieds-noirs nach Frankreich flohen, wo sie sich in Paris kennenlernten. Dort verkaufte sein Vater an einem Marktstand Frauenkleidung, bei dem Fitoussi, bis er 14 Jahre alt war, aushalf. Nach 25 Jahren erwarben sie ein Geschäft.[1]
Fitoussi hat einen Bruder Mikaël, der ebenfalls Schauspieler ist.[1]
Fitoussi begann ein Studium der Kulturvermittlung am Campus Cesnier der Universität Paris III, von dem er 1995 wegen eines Schummelversuchs temporär ausgeschlossen wurde.[2] Nachdem er in dieser Auszeit mit 18 Jahren ein Vorsprechen für ein Musikvideo gewonnen hatte,[1] brach er sein Studium im Alter von 20 Jahren ab. Durch den Videodreh erlangte er Werbeaufträge und nach mehreren Castings seine erste mehrjährige Rolle in der Sitcom St. Tropez von 1998 bis 2001, durch die er bekannt wurde. Dem folgten zunächst Episodenrollen und Fernsehfilme. Nachdem er St. Tropez verließ, trainierte er Method mit Jack Waltzer vom Actors Studio, der in Frankreich Praktika anbot.[2]
Ab 2005 spielte er eine Hauptrolle als Anwalt in der Justizserie Engrenages. Dort entdeckte ihn die Produktion der britischen Serie Mr Selfridge des Senders ITV, für die er ab 2012 drehte. In demselben Jahr begann er auch, in der französischen Serie Spin – Paris im Schatten der Macht zu spielen. 2013 trat er in dem amerikanischen Film World War Z auf. Zum Ende der fünften Staffel entschied er, Engrenages zu verlassen.[3] Folgend spielte er verstärkt in internationalen Serien wie Beowulf, Riviera und Beecham House, aber auch weiterhin in französischen wie Büro der Legenden, La Garçonne und The Reunion.