Étudiant en comédie à Londres, Rufus Sewell fait ses premiers pas d'acteur sur les planches de la capitale anglaise. En 1991, il apparaît pour la première fois sur grand écran aux côtés de la chanteuse Patsy Kensit dans le drame de Don Boyd, Twenty-One. Dès 1993, il incarne Tim, un personnage important dans Dirty Weekend, le thriller de Michael Winner. Un an plus tard, il voyage dans le temps aux côtés d'Emma Thompson en jouant le rôle de Marc Gertler dans Carrington de Christopher Hampton. Après avoir joué pour la télévision en 1995 (Henry IV et La Ferme du mauvais sort), il tient le rôle de Robbie Fay en donnant la réplique à Albert Finney dans Un Homme sans importance de Suri Krishnamma, puis enchaîne sur une autre production britannique en costume : Hamlet de Kenneth Branagh (1996).
Ce n'est qu'en 1997 que le comédien se révèle au grand public, perdu dans le labyrinthique Dark City, signé Alex Proyas. Loin de se cantonner dès lors aux grosses productions de science-fiction, Rufus Sewell reste tout d'abord fidèle à sa Grande-Bretagne natale, comme en témoigne sa participation à Martha, Meet Frank, Daniel and Lawrence en 1998. Puis c'est la traversée de l'Atlantique, avec Illuminata de John Turturro (1998), L'Elue avec Kim Basinger (2000) et Chevalier de Brian Helgeland (2001) qui lui permet de retrouver ses compatriotes Paul Bettany et Mark Addy. Acteur éclectique, Rufus Sewell aime varier les registres comme il le prouve en tournant dans son premier véritable film d'action, The Extremists, réalisé par Christian Duguay, passant de films en costumes tels que Hélène de Troie, au film d'aventure La Légende de Zorro aux côtés de Catherine Zeta-Jones et Antonio Banderas, en faisant un détour par la romance Paris je t'aime sous la direction de Wes Craven, l'un des 20 réalisateurs du film.
En 2006, l'acteur prête ses traits à Jasper dans la comédie romantique The Holiday de Nancy Meyers avec Cameron Diaz et Kate Winslet, et poursuit sa carrière en jouant dans le drame Amazing Grace et dans l'adaptation de Kevin Reynolds, Tristan & Yseult. Le thriller L'Illusionniste de Neil Burger offre l'opportunité à Rufus Sewell qui incarne le rôle du prince Leopold, de donner la réplique à Edward Norton, son rival dans le film. Après une première expérience dans l'univers des séries télévisées grâce à son premier rôle de roi dans Charles II : Le Pouvoir et la Passion, l'acteur britannique renouvelle ses performances dans d'autres séries comme Eleventh Hour ou John Adams.
Il reprend ensuite ses rôles de cinéma sous la férule de Fabrice Du Welz dans Vinyan avec l'actrice française Emmanuelle Béart. Son accent britannique lui permet d'interpréter le rôle de l'Anglais dans The Tourist (2010), collaborant ainsi avec Angelina Jolie et Johnny Depp avant d'être appelé à porter la série Zen en 2011 dans le rôle d'Aurelio. En 2012, le réalisateur Edward Hall l'engage dans Restless, une série britannique sur l'espionnage. L'acteur tourne la même année avec le réalisateur russe Timur Bekmambetov, dans la grosse production fantastique Abraham Lincoln : Chasseur de Vampires.