Stuart was born in Beckenham, Kent. He graduated from the Guildhall School of Music and Drama in 1993. Contemporaries at Guildhall included Daniel Craig, Ewan McGregor and Damian Lewis. He joined the Royal Shakespeare Company the same year and was cast as Burgundy in Adrian Noble's production of King Lear which starred Sir Robert Stephens.
Stuart made his big screen debut when Jerry Zucker offered him the role of Peter in his movie First Knight which starred Sean Connery and Richard Gere. Numerous TV appearances followed in acclaimed television dramas such as The Jury directed by Pete Travis, in which he played Charles Gore alongside Derek Jacobi and Gerard Butler; All the King's Men a 1999 BBC film based on the story of the 1/5th (Territorial) Battalion of the Norfolk Regiment, in which he played 2nd Lt. Frederick Radley alongside David Jason and Maggie Smith; P.O.W directed by John Strickland, in which he played Jewish prisoner of war Harry Freeman and Egypt in which he played Jacques Joseph Champollion-Figeac.
Stuart has appeared in two other drama documentaries for the BBC, Space Race directed by Christopher Spencer in which he played General Gaidukov and Nuremberg: Nazis on Trial directed by Michael Wadding in which he played Major Douglas Kelley.
Stuart most recently played Gavin in acclaimed Channel Four drama Clapham Junction directed by Adrian Shergold.