He was born in Glasgow in 1973. His first study was the violin, but his voice was recognised as his more important calling by his teachers at the Royal Scottish Academy of Music and Drama. He sang in the chorus of Opera North for four years.
Paterson sang with the English National Opera in a number of productions, including Mozart's Don Giovanni. He made his debut at the Salzburg Festival in 2007 as Fasolt in Wagner's Das Rheingold under Sir Simon Rattle. He first appeared at the Metropolitan Opera as Günther in Wagner's Götterdämmerung in 2009, under James Levine.
He sang in the Australian premiere of Shostakovich's 13th Symphony in 2008. His other concert repertoire includes Beethoven's 9th Symphony, Elgar's The Dream of Gerontius, Mendelssohn's Elijah, Verdi's Requiem and Handel's Messiah.