W 1958 kwintet reaktywował się jako sekstet, z dodatkowym udziałem Cannonballa Adderleya na saksofonie altowym i dokonał nagrania Milestones. Muzycznie, obejmowało ono zarówno motywy należące do przeszłości, jak i przyszłości jazzu. Davis (zręcznie wspomagany przez Coltrane’a) pokazał, że potrafi grać zarówno blues, jak i bebop, ale największą atrakcją jest utwór tytułowy, kompozycja Davisa oparta na skali doryckiej i eolskiej, w której Davis w pełnej krasie zaprezentował swój styl modalny, którego ważny element stanowi swobodna improwizacja, a który uczynił później swoim emblematem.
Nagrania z Gilem Evansem (1957–1963) W późnych latach pięćdziesiątych i wczesnych sześćdziesiątych Davis nagrał szereg albumów z Gilem Evansem, często grając nie tylko na trąbce, ale i na skrzydłówce. Pierwszy z nich, Miles Ahead (1957) wylansował jego wysoko cenioną grę w big-bandzie i sekcję na róg w aranżacji Evansa. Wśród melodii znalazły się The Duke Dave’a Brubecka oraz The Maids of Cadiz Léo Delibesa, pierwszy utwór europejskiej muzyki poważnej nagrany przez Davisa.