Olsen started his coaching career in January 1990, at the defending Danish champions Brøndby IF, and guided the club to two Danish championships. He put the team through tough fitness training which, even though it disgruntled some players, elevated the team into European top class, as Brøndby reached the semi final of the 1990–91 UEFA Cup with Olsen at the helm. With the notable exception of Nigerian international defender Uche Okechukwu, his dabblings in the transfer market were not equally successful. This caused anger among the amateur department of the club, whose youth scheme they felt Olsen overlooked. As the club faced financial hardship and results began to lack in 1992, Olsen was fired from the club in May.