He was born in Rutherglen, Glasgow and educated (sporadically) at Glenalmond school in Perthshire, Glasgow School of Art, and the Moray House College Of Education in Edinburgh. He moved into acting in his early twenties, taking the stage name Coltrane (in tribute to jazz saxophonist John Coltrane) and working in theatre and stand-up comedy.
His comic skills brought him roles in the television series The Comic Strip Presents (1982) and he was one of the stars of Laugh? I Nearly Paid My Licence Fee (1984). He soon moved into films, obtaining small roles in a number of movies such as Death Watch (1980), Scrubbers (1983), Absolute Beginners (1986) and Mona Lisa (1986). On television he also appeared in Tutti Frutti (1987), as Samuel Johnson in Blackadder (1987) (a role he later reprised in the more serious Boswell and Johnson's Tour of the Western Islands (1993)), and in a number of stand-up and sketch comedy shows.
He co-starred with Eric Idle in Nuns on the Run (1990), and played the Pope in The Pope Must Die (1991). His roles went from strength to strength in the 1990s with the TV series Cracker (1993-1996) and a Bafta award the stepping stone to parts in bigger films such as the James Bond films Goldeneye (1995) and The World Is Not Enough (1999), as well as giant Rubeus Hagrid in Harry Potter and the Philosopher's Stone (2001) and Harry Potter and the Chamber of Secrets (2002).
Married and has two children, Coltrane lives near Glasgow, and collects vintage cars.