Before the 1988–89 season, Malone agreed to a three-year deal to play with the Atlanta Hawks. The Hawks, featuring Dominique Wilkins, had won at least 50 games in the prior three seasons, and believed the free agent center was a missing piece to a potential championship team. During the season, Malone averaged 20.2 points with 11.8 rebounds, becoming the first and only player in professional history to average 20 points and 10 rebounds for four different teams. He was voted by a fan ballot to the 1989 NBA All-Star Game, which was his 12th straight and final appearance. Malone reached double figures in points in 75 of his 81 games and recorded double figures in rebounds 55 times. On February 4, 1989, he scored a season-high 37 points against the Phoenix Suns. The Hawks were eliminated in the first round of the playoffs by Milwaukee. In the series, Malone scored 21.0 ppg and had 12.0 rpg.