Willis spielte vor seiner NBA-Laufbahn für das Jackson Community College in Jackson County, Michigan und an der Michigan State University. Im NBA Draft 1984 wurde er von den Atlanta Hawks an elfter Stelle ausgewählt. Er spielte neun komplette Spielzeiten und zwei zusätzliche Spiele einer weiteren Spielzeit bei den Hawks, mit denen er oftmals in die NBA-Playoffs einzog. Er bildete in dieser Zeit mit Dominique Wilkins eines der besten Forward-Duos der Liga. 1992 wurde er in das NBA All-Star Game berufen. Er erzielte mit 18,3 Punkten und 15,5 Rebounds pro Spiel bis dato Karrierebestwerte.
Nachdem er anschließend zwei Jahre lang bei keinem NBA-Verein gespielt hatte, unterzeichnete Willis am 2. April 2007 einen 10-Tages-Vertrag bei den Dallas Mavericks. Er kam in fünf Spielen für die Mavericks zum Einsatz und ist seither, mit 44 Jahren und 224 Tagen, der zweitälteste Spieler, der je ein NBA-Spiel absolviert hat.[1]