Martin Brochu played his major junior hockey in the QMJHL, joining the Granby Bisons at the age of 17 in the fall of 1990. He played in 16 games during his rookie year, going 6-5-0 with a 3.76 gaa and one shutout. Brochu became the Bisons first-string goalie the following year, playing in 52 games. Midway through his final season in Granby, he was traded to the Hull Olympiques.
In 1993-94, Brochu signed a free-agent contract with the Fredericton Canadiens of the American Hockey League. That first year he played in 32 games and had a record of 10-11-3 with two shutouts and a 3.03 gaa. He started 44 games the next year, going 18-18-4 with a 3.51 gaa. In 1994-95, Brochu played for three teams, the Portland Pirates and Fredericton in the AHL and the Wheeling Thunderbirds of the ECHL. After spending the next year and a half with Portland, Brochu as called up to the Washington Capitals, where he sat on the bench in a backup capacity. He got his first taste of NHL action in 1998-99, when he played in two games for the Caps, losing both while allowing six goals. He also donned the pads for the Utah Grizzlies of the IHL and Portland that year, where he remained through the 1999-00 season. In 2000-01, Brochu tended goal for the St. John Flames, starting 55 games, going 27-19-5 with a 2.60 gaa. In the playoffs he led the Flames to the Calder Cup championship.
In the summer of 2002, Brochu was acquired by the Vancouver Canucks and went on to play one season with the club, spending the majority of his playing time with the AHL's Manitoba Moose before playing a mere nine games total in 2002-03. In a shortened season for Brochu, the former QMJHL netminder split his time with the QSHL's Verdun Dragons and Cherepovets Severstal of the Russian Elite League, before signing as a free-agent with the Pittsburgh Penguins in the summer of 2003.
In his first season with the Penguins organization, Brochu went on to split his time with the ECHL's Wheeling Nailers, the AHL's Wilkes-Barre/Scranton Penguins and the parent club in Pittsburgh.