À l'été 1948, Miles Davis, en collaboration avec l'arrangeur Gil Evans, qu'il a rencontré plusieurs années auparavant, décide de mettre son projet à exécution en se détachant des principes du Bebop pour participer à une nouvelle forme de Jazz. Installé à New York, il fonde un nouveau groupe, intermédiaire entre le big band et les petites formations Bebop. Ce sera un nonet (neuf musiciens), donc chaque section devra, dans l'esprit de ses créateurs, imiter l'un des registres de la voix humaine[12] : la section rythmique comprend contrebasse, batterie et piano, tenu par l'ancien batteur de Charlie Parker, Max Roach. Au niveau des cuivres, on trouve en plus de la trompette de Davis et du saxophone de Gerry Mulligan un trombone, un cor d'harmonie, un saxophone baryton et un tuba.

Le 18 septembre 1948, le nonet se produit pour la première fois en public, assurant la première partie du spectacle de Count Basie au Royal Roost de New York sous le titre « Nonet de Miles Davis, arrangement de Gerry Mulligan, Gil Evans et John Lewis ». Une dénomination inhabituelle qui trahit la volonté de créer une musique reposant largement sur les arrangements. Jouant une musique dont l'orchestration riche, les arrangements soignés et la relative lenteur rompent radicalement avec l'urgence du Bebop, le groupe est notamment remarqué par le directeur artistique des disques Capitol Records, Pete Rugolo, qui se montre très intéressé[12]. Après un contretemps dû à la grève des enregistrements de 1948, au cours de laquelle Miles refuse de rejoindre le groupe de Duke Ellington, le nonet entre finalement en studio début 1949 à New York pour une série de trois séances qui vont changer la face du Jazz. En quinze mois et avec de nombreux musiciens différents, le groupe enregistre une douzaine de morceaux, dont les titres Godchild, Move, Budo, Jeru, Boplicity et Israel. Six d'entre eux sortiront en 78 tours, le reste devant attendre les années 1950 et le célèbre album Birth of the Cool, sorti longtemps après les faits, pour voir le jour[12]. Le Cool Jazz est né, mais ce n'est pas une révolution immédiate : le nonet est rapidement dissout, et cette nouvelle musique mettra plusieurs années à s'imposer parmi les musiciens et le public Jazz. En 1949, Miles Davis effectue son premier voyage à l'étranger, participant le 8 mai au Festival International de Jazz à Paris, salle Pleyel. Co-dirigeant un groupe avec le pianiste Tadd Dameron, il rencontre l'élite intellectuelle et artistique parisienne de l'époque : Jean-Paul Sartre, Boris Vian, Pablo Picasso et surtout Juliette Gréco. Pour le trompettiste, c'est une véritable révélation. La France est en effet à l'époque un pays beaucoup moins raciste que les États-Unis, surtout au sein du milieu qu'il fréquente à Paris. Il a pour la première fois la sensation, comme il le dira dans son autobiographie « d'être traité comme un être humain »[12]. Tombé amoureux de Juliette Gréco, il hésite à l'épouser, ce qui serait tout simplement impensable dans son pays natal (à l'époque, les unions « mixtes » entre Noirs et Blancs sont encore tout simplement illégales dans de nombreux États américains). Ne voulant pas lui imposer une vie aux États-Unis en tant qu'épouse d'un Noir américain, et elle ne voulant pas abandonner sa carrière en France, il renonce et rentre à New York à la fin mai.

Mais, de retour aux États-Unis, la séparation d'avec Juliette Gréco et le milieu artistique parisien lui pèsent[13], et il réagit en replongeant dans l'héroïne. La drogue a des effets dévastateurs sur lui: laissant femme et enfants dans un appartement du Queens, il s'installe dans un hôtel de la 48e rue à New York, et va jusqu'à financer ses injections quotidiennes d'héroïne grâce à des prostituées[14]. Sa maison saisie par une société de crédit, il tourne avec d'autres drogués notoires, notamment au sein de l'orchestre reformé de Billy Eckstine, et se retrouve en prison à Los Angeles, suite à une descente de police.

Les années suivantes, Davis continue à enregistrer avec de nombreux artistes très cotés, tels que Charlie Parker, les chanteuses Sarah Vaughan et Billie Holiday, Jackie McLean, Philly Joe Jones ou Sonny Rollins. Il fait également la connaissance d'un jeune saxophoniste, John Coltrane, avec qui il joue brièvement à l'Audubon Ballroom de Manhattan. Mais, malgré l'intervention énergique de son père, qui le ramène chez lui à East St Louis et va même jusqu'à le faire arrêter par la police, il ne parvient pas à décrocher de la drogue. C'est après la rencontre en 1953 avec la danseuse Frances Taylor, qui va devenir sa seconde épouse, qu'il réussira à se désintoxiquer[15]. Après une difficile lutte contre son addiction à l'héroïne, dans la ferme de son père, il émerge en février 1954 et réunit un nouveau sextet qui compte notamment le batteur Kenny Clarke et le pianiste Horace Silver. Ensemble, ils posent les bases d'un nouveau style, qui deviendra après le Bebop et le Cool la « troisième vague » du Jazz moderne : le Hard Bop. Réaction contre le Cool Jazz qu'il a lui-même lancé, ce nouveau style plus énergique (sans atteindre les sommets du Bebop) est également plus simple harmoniquement que le Bebop. Il est notamment influencé par le Rhythm and blues, mais aussi par une nouveauté technologique, le disque 33 tours, qui permet des morceaux beaucoup plus longs et développés[15]. Plusieurs morceaux fondateurs du Hard Bop verront le jour sur l'album Walkin': en particulier Walkin' le titre éponyme, mais aussi Airegin (anagramme de Nigéria), Oléo et Doxy composés par Rollins sur l'album Bags' Groove. La même année sort sur ce nouveau format l'album Birth of the Cool, compilation des morceaux enregistrés par le nonet pionnier du Cool Jazz. Devenant dans l'esprit des auditeurs et des critiques un jalon dans l'histoire du Jazz Moderne, le disque donne un sérieux coup de pouce à la carrière renaissante de Miles. A Noël, il réalise avec Thelonious Monk, Kenny Clarke, Percy Heath et Horace Silver une séance considérée comme essentielle pour le développement de son style propre. 1954 est l'année charnière de Miles Davis qui aura transformé un bon trompettiste en un jazzman de génie, passé maître dans l'art du solo, aux répertoires élargis et ayant son champ des sonorités désormais défini : un son résonnant de la trompette ouverte et un timbre assourdi, introspectif de la sourdine.[16] Au Newport Jazz Festival de 1955, l'interprétation de Miles Davis de 'Round Midnight, un thème de Thelonious Monk, est saluée par une standing ovation doublée d'un immense succès critique : la carrière du trompettiste, sérieusement mise en péril par ses problèmes de drogue, est définitivement relancée.