After graduating from Iona, Malone then became a CYO basketball coach for the Church of the Most Precious Blood, Manhattan then became junior varsity basketball coach at Power Memorial Academy in 1967. Malone also enrolled at New York University and graduated with a master's degree in physical education in 1968. From 1970 to 1976, Malone was varsity basketball coach at Power Memorial and led Power Memorial to two city championships. During his six-season stint, Malone earned three "Coach of the Year" honors.
Malone was named as the first head coach (1995–96) of the Toronto Raptors, one of two 1995 NBA expansion teams in Canada. Malone was appointed the job by the Raptors' general manager of the time, Isiah Thomas. Malone was long considered the NBA's leading authority on defending Michael Jordan, particularly after orchestrating Detroit Piston defenses that kept Jordan's Bulls out of the NBA Finals for some time. Malone only lasted one season as head coach of the Raptors, going 21-61, but handing the championship Bulls one of their few losses that season. Following his time with the Raptors, Malone served as an assistant coach with the Indiana Pacers, New York Knicks, Detroit Pistons and as a consultant with the Seattle SuperSonics. He was the interim head coach of the Cleveland Cavaliers in 2004–05.
On July 3, 2007, Malone was one of four assistants hired to serve under new Orlando Magic head coach Stan Van Gundy. Malone's son, Mike, began the 2014 season as the head coach of the Sacramento Kings, but has since been fired by team management for a slow start. On June 25, 2013, he was hired as an assistant coach under his son at the Kings. However, on October 23, 2013, he announced that he would be leaving the Kings. On May 30, 2014, Malone was one of three assistants hired to serve under new Detroit Pistons head coach Stan Van Gundy.
The following assistant coaches who worked for Malone had later become head coaches:
Darrell Walker, who served as an assistant coach under Malone for the first Toronto Raptors season in 1995–96, succeeded Malone as Raptors head coach in 1996 and remained head coach until the middle of the 1997–98 season. Walker later was head coach of the Washington Wizards in the later half of the 1999–2000 season.
John Shumate, who also served as assistant coach for the inaugural Raptors team, continued to be an assistant for the Raptors until 1998. In 2003, Shumate was head coach for the Phoenix Mercury of the WNBA.