In March 2004 John Vincent, a former speaker of the Montana House of Representatives entered the race and criticised Schweitzer for taking both sides on some issues. In the end Schweitzer easily won the Democratic primary. Three days after the primary Schweitzer addressed the Montana Democratic Convention, gave a bear hug to his defeated rival, and said he would bring a new kind of leadership to Montana.
Incumbent Governor Judy Martz had a difficult term of office with her approval ratings as governor going as low as 20%. In August 2003 she announced she would not run for re-election as she wanted to spend more time with her family. Lieutenant Governor Karl Ohs was expected to enter the Republican primary race but decided not to.
Montana Secretary of State Bob Brown, conservative businessman Pat Davison and State Senators Ken Miller and Tom Keating competed for the nomination. Brown was seen as the favorite in the primary but was attacked by Pat Davison for being 'liberal on taxes.' Brown was the only one of the candidates who refused to sign a pledge not to raise taxes as he said he wanted to keep all options open as governor.
In mid summer polls showed Schweitzer had a 10-point lead over Brown, but by October the gap had closed to only 4 percent.
Schweitzer campaigned with plans to lift Montana from its position at the bottom of all 50 states in wages. He called for new uses to be found for crops like mint and for small businesses to pool in purchasing health care. He also supported opening the border with Canada to allow consumers to get cheaper prescription drugs from Canada.
Brown said that the Democrats harmed business growth and job creation. He touted his government experience including 26 years in the Montana legislature and accused Schweitzer of taking hypocritical stands.
Schweitzer won the election to become the first Democrat in 20 years to win an election for governor. According to the exit polls Schweitzer obtained two-thirds of the vote from over 65s and from independent voters. This was despite President George W. Bush winning Montana very easily over John Kerry.