McCallum's first political office was reeve of the United Townships of Moulton and Sherbrooke. In 1863 he ran for a seat in the Legislative Assembly but was narrowly defeated. He ran again in the first general election after Confederation, and was elected for the Dominion Parliament and the Ontario Legislature as the representative for Monck.
After the abolisment of dual representation, McCallum resigned his seat in the Legislature. He ran for a seat in the House of Commons in 1872 but was defeated. He won the seat two years later in the 1874 election. McCallum held this position until 1887, when he was appointed to the Senate. During his political career, McCallum pressed for the enlargment of canals and the construction of an all-Canadian railway.