His first four years as a head coach saw Mjelde win both the league and the cup in Norway. Retiring as a player after the 2001 season, Mjelde became the new coach for Brann's reserve team in the Norwegian Second Division. The year after, Brann's head coach, Teitur Thordarson left the club. In January 2003, after only one year's experience as a coach, Mons Ivar Mjelde was appointed head coach in SK Brann. The season resulted in Brann finishing 6th, a major improvement from the previous year. The following year he guided Brann to a bronze medal in the premiership. They also won the cup, the first trophy in 22 years.