He coached Selkirk High School and Selkirk Youth club. During his time at Selkirk Youth Club he took the team to three successive Youth League Cup finals, winning the title in 2003. Selkirk's promotion to the Scottish Premiership One in 2008 was described as a testament to Graham's coaching abilities, as 15 of his protégés were involved in the squad.
In 2011, Graham became the coach at Scottish Permier One side, Heriot's Rugby Club in Edinburgh. Graham has also coached the U18 Scottish team.