When local favourite James Agg-Gardner stood down rather mysteriously in 1895, the local Conservatives had to cast far and wide for a suitably eminent and wealthy replacement (MPs were still unpaid). They settled on Colonel Francis Shirley Russell, an Aberdeenshire landowner and soldier with a distinguished record in the South African wars who had twice failed to get elected by his native county. It was a tough call for an outsider to follow Agg-Gardner but the 1895 election saw a national swing return the Marquess of Salisbury to office with a crushing Conservative and Unionist majority. The colonel was safely elected in Cheltenham, albeit with a reduced majority, seeing off both his official Liberal opponent and the first independent labour candidate, Mr Hillen, who polled just 23 votes.
Frank Russell was an active and eloquent MP, speaking often with a predictably expert take on farming and military affairs and a devastating dry wit which he deployed mercilessly at dozy military bureaucrats in particular. His career in the military continued and he was promoted to Major-General in 1897 but the 1900 election saw him retire from frontline politics in favour of the returning Agg-Gardner.