Malcolm's career started in 1998 when he signed a professional contract with St Johnstone. He was sent on loan to struggling Third Division side Cowdenbeath to gain experience, where he managed to stave off the possibility of finishing bottom of the Scottish league thanks to a win in the final game of the season against fellow strugglers Montrose. When Malcolm finished his spell at St. Johnstone, he moved south of the border to Plymouth Argyle, where he played extensively in the reserves, although he was unable to make inroads in the first team.
Ross County & Ireland
At the beginning of the 2003–04 season, Malcolm signed for Ross County, and he played the first game of his season for the team in the Scottish League Challenge Cup quarterfinal defeat to Inverness. Malcolm helped Ross County consolidate their position in the league during the 2003–04 season, though towards the end of the year he played much less frequently. This stemmed indirectly from a spate of yellow and red cards. He was first sent off for causing injury to Laurie Ellis, and this was followed by a second for a challenge on Ian Harty. Between February and May, Malcolm played just five games for the side. He was then dropped from the team after Christmas 2004. In February 2005, Stuart departed Ross County to join League of Ireland Premier Division side Drogheda United. Stuart became a regular in the team during the 2005 season and made an immediate impression for the County Louth side. Despite a strong first season at Drogheda United, Stuart's one-year contract at the Drogs was not renewed and he became a free agent. It did not take Stuart long to find a new club as he signed for newly promoted Premier Division outfit Dublin City in January 2006. At his new club, he again became regular in the side and became an integral part of City's push up the table. Stuart's career at Dublin City was cut short as the club went out of existence in July 2006 due to financial difficulties.
Return to Scotland
He then returned to Scottish football by signing for Alloa Athletic, where he made his debut in a 6–1 drubbing at the hands of Cowdenbeath. Later the same month, he picked up his first of three red cards in that term, two of which came in successive appearances. During March 2007, Malcolm left Alloa and signed for Montrose, but he was released by Montrose at the end of the season.
Return to Ireland
Immediately after his release from Montrose, Malcolm returned to Irish football by agreeing to sign for Eircom League First Division outfit Shelbourne. The deal was brokered by Malcolm's former manager at Dublin City, Dermot Keely, who was then manager of Shels. Keely brought Malcolm to Tolka Park to help add much needed experience and bite to the Shelbourne side who were struggling in their first season in the FAI First Division after the Tolka Park outfit's demotion to the second tier of Irish football. Stuart made his Shelbourne debut in a 1–0 victory against Wexford Youths at Tolka Park on 6 July 2007. He soon scored his first Shelbourne goal during a 5–2 victory over Kilkenny City at Buckley Park. After making 17 appearances for Shels, Malcolm departed in January 2008 to join Finn Harps.
Malcolm was appointed assistant manager to Brian Kerr at Scottish League One side Albion Rovers in May 2017. After the club were relegated to Scottish League Two, Kerr and Malcolm both resigned from their positions after just a year. Malcolm joined Brian Kerr at Lowland League team East Kilbride at the start of the 2018-19 season. Kerr left to be Gary Caldwell's assistant at Partick Thistle in October 2018. Malcolm remained as caretaker manager and eventually was placed in charge until the end of the season. Malcolm would go on to lead East Kilbride to their second Lowland League title in March 2019. Malcolm returned to former team Forfar Athletic after being appointed the club's new manager in November 2019.
