For Miles in the Sky, Davis and his quintet pulled further away from conventional jazz and more toward jazz-rock fusion. The album's compositions are extended and groove-oriented, and in the case of the opening track "Stuff", the band lays a rhythm with a simple 4 4time signature from rock music, which is embellished by Hancock's electric piano. According to All About Jazz's C. Michael Bailey, Miles in the Sky is one of six albums by Davis' quintet between 1965 and 1968 that introduced the poorly defined jazz subgenre post-bop.
In a contemporary review, Down Beat magazine called Miles in the Sky one of the best albums by Davis and his second quintet because of how it shows he had been influenced by Ornette Coleman and John Coltrane: "even as Miles denies it, for their assault on the popular song has pushed Miles along the only path that seems open to him, an increasingly ironic detachment from sentiment and prettiness".
In a retrospective review for Allmusic, Stephen Thomas Erlewine found it less adventurous than Nefertiti (1968): "Intriguing, successful jams in many respects, but ... this is less visionary than its predecessor and feels like a transitional album – and, like many transitional albums, it's intriguing and frustrating in equal measures." Hernan M. Campbell of Sputnikmusic was more enthusiastic and praised the musicianship throughout, particularly that of Williams, whose drumming he found "mind-blowing". Campbell felt that Miles in the Sky should not be overlooked because it marked the beginning of Davis' electric period and was one of the defining jazz fusion albums.