He was spotted by Hull City manager Billy McCracken while playing amateur football for Washington Colliery and signed for the Yorkshire club in October 1926 at the age of 17.
Despite their good cup form that season the team struggled in Division Two and were heading for relegation when soon after the semi-final he returned to his native North-East with a £3,750 move to Newcastle United in May 1930.
He took no part all in Newcastle's FA Cup run which saw the team beat Arsenal 2–1 in the final and on 25 June 1932 he signed for Sheffield Wednesday in a £3,250 deal.
As Wednesday struggled near the bottom of Division One, Starling joined Aston Villa for £6,900 on 6 January 1937, just a day after they had rejected a huge bid for Jackie Robinson from Arsenal.
He remained on the books at Villa Park throughout World War II winning the Football League North in 1944, although he did make guest appearances for Northampton Town, Walsall and Sheffield Wednesday during the conflict.