A talented forward, nicknamed the "Prince of Dribblers", Fitchie was born in Edinburgh and played football as an amateur. He appears to have travelled a lot, and his career was rather eclectic as a result; he played for a variety of clubs, and the dates of some of his tenures are not known. Having started out at West Norwood, Fitchie joined Woolwich Arsenal when he was 19, in November 1901. He made his debut against Gainsborough Trinity in a Second Division match on 8 February 1902, and scored twice as Woolwich Arsenal rolled out 5–0 winners. However, being unable to fully commit to the team, he was only in the Woolwich Arsenal side intermittently. As an amateur he was free to play for other team and often guested for other London sides in addition to Arsenal, including Fulham, London Caledonians and even Tottenham Hotspur — although as they were not at this time Arsenal's deadly local rivals, otherwise this would have raised few eyebrows at the time. He played two games for Tottenham scoring one goal. Fitchie's main club, however, was Woolwich Arsenal and it seems he played mostly for them while he was in London. It wasn't until the 1904–05 season did he have any sort of decent run in the side, though; he scored six goals in 9 league games that season, Arsenal's first in the First Division. Fitchie's ability was such that he was called up to play for Scotland, against Wales on 6 March 1905, which Scotland lost 3–1. In all he won four caps for his country, scoring one goal — the only goal of the game against Ireland on St Patrick's Day 1906. He was still a regular for Woolwich Arsenal, scoring 9 league goals in 1905–06 and reaching an FA Cup semi-final the same season. Fitchie left Arsenal in mid-1906 back to his native Scotland, and played for Queen's Park for two years. He also spent some time in Southern England during this period, occasionally appearing for Norwich City and Brighton & Hove Albion. He returned to Woolwich Arsenal in 1908, and he played another full season there; he scored 10 goals in twenty-one games, making him Arsenal's top scorer; that season they finished sixth in the First Division, which would remain their highest-finishing position until 1925–26. In all, he played 63 times for Arsenal and scored 30 goals. After leaving Arsenal, Fitchie joined a touring team known as The Pilgrims, a sidecomposed of British players that toured the US in October and November 1909. After returning to England, Fitchie played for Glossop North End between 1909 and 1911 and Fulham for a second spell in 1912.
