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.
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, is the head coach of the Sacramento Kings. 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.