During the summer of 1953 Graham was "called up" by the Dons and his talent was such that he was pitched straight into the first team at outside right where he made a tremendous impact in his first season. Leggat had the attributes normally associated with a top class player: natural ability, mental and physical agility, speed and a knack of improvising to outwit an opponent. His introduction to the Dons side in 1953 was probably the biggest factor in turning Aberdeen from a side that habitually came close, into the side that rose to the top of Scottish football in 1955. Following the title triumph of 1955, Graham's goalscoring was a big factor in the Dons 1955-56 League Cup success, with Leggat scoring 9 goals in 10 ties. Including the winner in the final itself v St Mirren at Hampden.

With several Scottish under 23 caps behind him Graham, was promoted to the full international side for the England game at Hampden on April 14th 1956. The Scots were seen as lambs to the slaughter by the English press but a remarkable lobbed goal by the debutant Leggat put Scotland ahead in the second half and only a last gasp equaliser prevented the home side registering their first Hampden win over the "Auld Enemy" in almost 20 years. A second cap against Wales in Cardiff in October 1956 seemed to herald a long international future for Graham but injury kept his name out of the frame for further internationals in late 1956 and it wasn't until October 5th 1957 that the winger got another call to do battle against Northern Ireland in Belfast. Again Leggat did the honours with the Scots only goal in a 1-1 draw but disaster was only weeks off as Graham broke a leg in late October and was sidelined for much of the season.

A trained PE teacher, Leggat confounded the critics who wrote him off following his leg break and made a full recovery. With Scotland heading to Sweden for the 1958 World Cup Finals the selectors picked the Dons' star for a warm up friendly against Hungary at Hampden in May 1958 and Graham took the opportunity to seal his place in the Scottish squad to travel to Sweden. A final warm up friendly in Poland was the curtain raiser to the main event the World Cup itself and the Scots, with Leggat prominent, did well to hold highly fancied Yugoslavia to a 1-1 draw. The next game was a real tester against Paraguay but Scotland suffered a 3-2 loss to the South Americans although Graham had the satisfaction of equalling Jock Hutton's 32 year old 7 cap club record.

Leggat was omitted from the side to face France in Scotland's final game thus denying him the chance to set a new club mark in the World Cup. Unfortunately, from the fans point of view Leggat's exposure to international soccer exposed him also to the chequebook wielding clubs form the south of the border and in August 1958 the inevitable happened when Graham was transferred to Fulham for the incredibly low sum of £16,000. At Craven Cottage Leggat went on to win 11 more caps before his departure from the international scene in 1960. He remained a Fulham player until January 1967 when he joined Birmingham City and played one final season of senior soccer with Rotherham in 1968-69 before calling it a day. Graham had a short spell on the backroom staff at Aston Villa before non-league Bromsgrove tempted him back as a player but before long he had emigrated to Canada and became a leading light in the development of Canadian soccer.