Doué d'un sens inné de la danse, Gregory Hines fait ses premiers pas à Broadway à l'âge de huit ans, accompagné de son frère Maurice, son aîné de quatre ans. Lorsque Gregory a dix ans, ils se produisent à l'Olympia à Paris dans un spectacle de Roger Pierre et Jean-Marc Thibault. De 1964 à 1972, rejoints par leur père, ils forment le trio Hines, Hines and Dad et triomphent sur les planches de nombreux cabarets ainsi que dans des shows télévisés.
Star américaine des claquettes, Gregory Hines laisse parfois ses fers au vestiaire pour prêter sa silhouette sportive et élancée au cinéma. Ses premiers pas d'acteur effectués dans La Folle histoire du monde (1981) de Mel Brooks, il apparait, toujours en 1982, en officier de police judiciaire dans Wolfen (Michael Wadleigh, 1980). Après deux films restés inédits en France (Deal of the century, 1983, William Friedkin ; The Muppets take Manhattan, 1984, Frank Oz), le danseur-acteur triomphe dans Cotton Club (1984) de Francis Ford Coppola, où il interprète le rôle dramatique d'un danseur noir des années 1920. Hines poursuit dans le registre de la danse avec Soleil de nuit (Taylor Hackford, 1985) au côté d'Isabella Rossellini et du danseur Michail Barychnikov. Il est moins convaincant dans la peau d'un flic pendant la guerre du Vietnam (Saigon, l'enfer pour deux flics, Christopher Crowe, 1987). Gregory Hines chausse une nouvelle fois ses chaussures ferrées dans le film "Tap" (Nick Castle, 1988) au côté du futur maître des claquettes américaines Savion Glover.
Très actif sur les planches de Broadway, Gregory Hines est nommé à plusieurs reprises au Tony Award pour ses prestations dans Eubie, Comin'up town et Sophisticated ladies.
Gregory Hines tient le rôle du grand danseur de claquettes Bill "Bojangles" Robinson dans le téléfilm américain Bojangles (Joseph Sargent, 2001).