Interstellar Space consists of an extended duet suite in four parts with the drummer Rashied Ali, and was recorded at the Van Gelder Studio on February 22, 1967, the week after the session that produced Stellar Regions. As a result, the melodies often overlap; "Venus" has the same melody as the title track of the previous LP, "Mars" quotes the melody of what became known as "Iris", and many note choices and runs are similar.
At the beginning of most of the songs, Coltrane plays chime-like bells, while Ali sets a shifting pattern on the drums; then the theme is stated by Coltrane on tenor saxophone. The album is an important[according to whom?] example of highly improvised free jazz, which was Coltrane's principal interest in the latter part of his career. Coltrane's improvisations are thus extremely free here, stating tacit modes and harmonies briefly and modulating constantly, fitting extremely dense, twisting expressions into breath-length phrases. The folkish "Venus" is probably the most accessible number; "Saturn", the longest piece, does feature hints of swing by song's end. Its melody is rather similar to the canonical, almost cantor-like quality of the material on Stellar Regions.
The original album featured four tracks: "Mars" (titled "C Major" in the ABC/Paramount session sheets), "Venus" (titled "Dream Chant" in the session sheets), "Jupiter", and "Saturn". Two further tracks from the session, "Leo" and "Jupiter Variation", later appeared on the compilation album Jupiter Variation in 1978. A 2000 CD reissue collected all of the tracks from the session, including false starts for "Jupiter Variation" in the CD's pregap.