Scheer was elected for the first time in the 2004 election. He was elected in the riding of Regina—Qu'Appelle for the Conservative Party. With that election, he beat the New Democratic Party MP Lorne Lystrom. He won by over 800 votes. He was elected again in the 2006 election. He beat Lystrom again by 2740 votes.