Pod koniec lat 30. zadebiutował na teatralnych deskach Nowego Jorku. Punktem przełomowym okazał się dla niego broadwayowski musical Kumpel Joey (1940). Na wielkim ekranie debiutował u boku Judy Garland w musicalu Dla mnie i mojej dziewczyny (1942). Już na samym początku jego kariery filmowej można było dostrzec rewolucyjne podejście aktora do formuły musicalu, a także jego oryginalny styl tańca – bardziej dynamiczny, z licznymi wpływami baletu i tańców afroamerykańskich. W przeciwieństwie do dotychczasowego króla filmów muzycznych, Freda Astaire’a, Kelly tańczył całym ciałem, jego płynne i znakomite ruchy były wyzbyte dostojności, a strój po raz pierwszy w historii musicalu swobodny, codzienny.
W kolejnych latach występował u boku Rity Hayworth w Modelce (1944), Judy Garland w Thousands Cheer (1943) i Piracie (1948), a także Franka Sinatry w musicalach: Podnieść kotwicę (1945), Zabierz mnie na mecz (1949) i Na przepustce (1949). Ten ostatni był również pierwszym filmem, który Kelly współreżyserował ze Stanleyem Donenem. W 1944 wstąpił do marynarki, gdzie realizował filmy instruktażowe dla armii.