On December 11, 2006, the St. Louis Blues hired Murray to replace Mike Kitchen as head coach after a seven-game losing streak. He coached the Blues to a record of 33–36–13 in his first full season as coach in 2007–2008. On April 10, 2009, Murray coached the Blues from a 15th place showing in the Western Conference at the All-Star Break to a 25–9–7 record down the stretch to clinching the sixth playoff spot, marking the team's first Stanley Cup playoffs appearance since the 2004–05 lockout. Murray's Blues took on the Vancouver Canucks in the opening round of the 2009 Stanley Cup Playoffs and were swept. Murray was named a finalist for the Jack Adams Award for coach of the year during the off-season but lost to Claude Julien of the Boston Bruins.