Cheveldae began his junior ice hockey playing career in the 1985–86 WHL season with the Saskatoon Blades. Cheveldae was selected in the 4th round by the Detroit Red Wings in the 1986 NHL Entry Draft. Cheveldae remained with the Blades until the end of the 1987–88 season before leaving for the professional ranks. For the 1988–89 season, Cheveldae went to the Red Wings' minor league affiliate, the Adirondack Red Wings, in the American Hockey League. His level of play earned him a call up to the NHL, where he served two games in net for the Red Wings, and made him the fourth goaltender on the Red Wings roster behind Greg Stefan, Glen Hanlon and Sam St. Laurent. While Detroit's goaltending lineup would remain the same for the 1990–91 season, Cheveldae ascended the depth chart, going from goaltending in the AHL to being in Detroit's goaltending tandem with Hanlon, as Stefan suffered career ending injuries while St. Laurent never ascended beyond the role of a third goaltender at the NHL level despite his minor league success. From the 1990–91 season to the 1992–93 season, Cheveldae was Detroit's starting goaltender. With Detroit not settling on a consistent backup, Cheveldae was Detroit's goaltending workhorse for those seasons, playing no fewer than 65 games in each of those seasons and playing an astounding 72 games during the 1991–92 season, earning him the right to play in the 1992 NHL All-Star Game. While Cheveldae had success during the regular season, the team would never go deep into the playoffs during those seasons, leaving Cheveldae to be the scapegoat for Detroit's inability to succeed in the playoffs. In the 1993–94 Season, Chris Osgood emerged from the minors to become Detroit's new starting goaltender. Despite having a successful season, Cheveldae ended up traded to the Winnipeg Jets as part of a package deal which brought Bob Essensa and Sergei Bautin to Detroit on March 8, 1994. Cheveldae missed the playoffs with the Jets. While in Winnipeg, Cheveldae never achieved the level of success he had with the Red Wings. While he served the Jets as starting goaltender during the abbreviated season in 1994–95 and the beginning of the 1995–96 season, the Jets eventually opted to go with Nikolai Khabibulin as their starter. Cheveldae was traded to the Philadelphia Flyers on February 27, 1996, for Dominic Roussel, and he was assigned to the minor league affiliate Hershey Bears. On August 27, 1996, Cheveldae signed with the Boston Bruins. Cheveldae served two games that season while spending most of his time on loan to the Fort Wayne Komets of the International Hockey League. Cheveldae was not re-signed at the end of the season. Cheveldae played his final season of professional hockey during the 1997–98 Season, skating for the Las Vegas Thunder of the IHL.
Cheveldae would return to the Saskatoon Blades as an Assistant coach for two seasons following his playing career. Cheveldae was also on roster for the First Annual Detroit Red Wings Alumni Showdown in Detroit on February 19, 2005, as the Red Wings alumni team would lose to the Maple Leafs alumni team 10–9 in a shootout. According to The Hockey News, Cheveldae is currently working as a firefighter at the Dundurn military base in Saskatchewan.
