Anthony Robert McMillan néven született Glasgow-ban, ott végzett művészeti iskolát, majd festői képességeit kétségbe vonva a színészetre váltott, radikális társulatokban kezdett játszani. A Coltrane művésznevet John Coltrane dzsesszzenész tiszteletére vette fel.
Első filmszerepét 1979-ben kapta, ezután filmekben és tévésorozatokban tűnt fel kisebb szerepekben, puszta testméretei is segítettek neki, hogy kitűnjön a tömegből.
A nyolcvanas években egyre többször kapott nagyobb szerepeket, többek között Derek Jarman Caravaggiójában, melyben a kardinálist alakította, vagy Kenneth Branagh V. Henrikjében, ahol Falstaffot játszotta.
