Stevenson was born in Lisburn, in County Antrim, Northern Ireland, the second of three sons of a Royal Air Force pilot father and an Irish mother. He moved with his family to Lemington, Newcastle upon Tyne, England, in 1972, at the age of eight, and later to Cramlington, Northumberland, where he was brought up. Stevenson attended Bristol Old Vic Theatre School, graduating at the age of 29. In 2011, Stevenson appeared in the film Kill the Irishman, based on the book To Kill the Irishman, as Danny Greene, an Irish American mobster who took on the Italian mob in Cleveland, Ohio in the 1970s. He worked with Kenneth Branagh, this time as a director, in the adaptation of Marvel Comics' Thor, starring in the role of Volstagg, one of Thor's trusted comrades. Also that year, he played Porthos in Paul W.S. Anderson's adaptation of The Three Musketeers. On 8 July 2011, Stevenson was cast as Firefly in G.I. Joe: Retaliation (which was released in 2013).