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, often with rhythms that, according to Stephen Thomas Erlewine, "are straightforward, picking up on the direct 4/4 beats of rock, and these are illuminated by Herbie Hancock's electric piano". In the opinion of All About Jazz's C. Michael Bailey, Miles in the Sky was 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, 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.