Nadat hij in 1944 zijn middelbare schooldiploma had gehaald, verhuisde Davis naar New York City om aan de Juilliard School of Music te studeren.
Toen hij in New York aankwam, besteedde hij het grootste deel van zijn tijd aan het proberen in contact te komen met Charlie Parker, ook al hadden sommige mensen hem gezegd dat hij dat niet moest doen. Toen hij Parker gevonden had, raakte Davis betrokken bij jamsessies die elke avond plaatsvonden in twee nachtclubs van Harlem, Minton's Playhouse en Monroe's. Andere beroemde musici zoals Thelonious Monk en Kenny Clarke namen ook deel aan deze sessies.
Davis verliet Juilliard vroegtijdig, nadat hij eerst toestemming aan zijn vader had gevraagd. Hij hield niet van de lessen op Juilliard omdat hij vond dat ze teveel gericht waren op klassieke Europese en "blanke" muziek. Hij zei ook dat zijn Juilliard-lessen hem hielpen de muziektheorie te begrijpen.
Hij begon professioneel te spelen in vele jazzgroepen en trad op in verschillende 52nd Street clubs met Coleman Hawkins en Eddie "Lockjaw" Davis. In 1945 ging hij voor het eerst een opnamestudio in, als lid van de groep van Herbie Fields. In 1946 maakte hij zijn eerste opname als bandleider, met een groep genaamd "Miles Davis Sextet plus Earl Coleman en Ann Hathaway". Hij maakte in die tijd niet veel opnamen als bandleider.
Rond 1945 stopte Dizzy Gillespie met werken met Parker en Parker nam Davis in dienst als Gillespie's vervanger in zijn kwintet. In de groep zaten ook Max Roach aan de drums, Al Haig (later vervangen door Sir Charles Thompson en Duke Jordan) aan de piano, en Curley Russell (later vervangen door Tommy Potter en Leonard Gaskin) als bassist.
Met Parker's kwintet nam Davis verschillende keren op. Hij had een solo op Parker's signature song, "Now's the Time". Deze solo leidde tot het begin van een jazzstijl die "cool jazz" werd genoemd. De groep toerde ook door de Verenigde Staten. Tijdens een tournee in Los Angeles kreeg Parker een zenuwinzinking en ging hij voor enkele maanden naar het Camarillo State Mental Hospital. Davis kwam vast te zitten in L.A. Hij verbleef bij, en musiceerde met jazzmuzikant Charles Mingus. Later kreeg hij een baan bij Billy Eckstine op een Californische tournee die hem terugbracht naar New York. In 1948 keerde Parker terug uit Los Angeles, en Davis sloot zich weer bij zijn groep aan.
De muzikanten in Parkers groep konden niet zo goed met elkaar opschieten. Parkers gedrag was onvoorspelbaar vanwege zijn drugsverslaving. Davis en Roach waren het er niet mee eens dat Parker Duke Jordan als pianist inhuurde en hadden liever Bud Powell gehad). In december 1948 verliet Davis de groep na een ruzie met Parker in de Royal Roost. Hij begon meer onafhankelijk te werken met verschillende groepen in New York.