De gehele bezetting van Empyrean Isles werd opnieuw ingezet voor de opnames van Maiden Voyage, waarbij Freddie Hubbard zijn kornet verwisselde voor een trompet. Een nieuw lid was saxofonist George Coleman, die juist Miles Davis' quintet had verlaten. De solo's die hij in het album op tenorsaxofoon uitvoert worden tot zijn beste werk gerekend.
Volgens de archieven van Blue Note werden op 11 maart 1965 opnames gemaakt van Maiden Voyage, Little One en Dolphin Dance, zes dagen eerder dan de definitieve opnames. Freddie Hubbard speelde net als in Empyrean Isles op kornet en Stu Martin drumde in de plaats van Tony Williams. De opnames werden afgekeurd en zijn verloren geraakt.
This music attempts to capture its vastness and majesty, the splendor of a sea-going vessel on its maiden voyage, the graceful beauty of the playful dolphins, the constant struggle for survival of even the tiniest sea creatures, and the awesome destructive power of the hurricane, nemesis of seamen.
- Herbie Hancock
Maiden Voyage is Hancocks tweede conceptalbum en heeft veel overeenkomsten met Empyrean Isles, zijn vorige conceptalbum dat in het teken staat van een geheimzinnige eilandengroep. Deze mysterieuze sfeer komt terug in Maiden Voyage. In de hoestekst legt Hancock uit dat de muziek een poging was om de mystiek en de uitgestrektheid van de majestueuze zee weer te geven. De titel Maiden Voyage slaat op een term uit de scheepvaart dat slaat op de eerste reis van een schip, nadat het de dokken verlaat. De folklore kent veel legenden rond deze reis, waardoor het in de loop der tijd omringd is geraakt door bijgeloof.
De hoestekst van de originele uitgave werd deels geschreven door Nora Kelly, die ook de hoestekst voor Empyrean Isles schreef. Zij beschrijft de setting van elk van de vijf nummers. Het concept van de oceaan klinkt op verschillende manieren door in de muziek, zoals de ruimte die de solisten gebruiken en de trage dynamiek van het drumwerk van Tony Williams, die doet denken aan de golfslag op het strand.[5]
De muziek op het album is aanmerkelijk ingetogener dan die op Empyrean Isles. Herbie Hancock liet de funk achterwege in de vijf melodieuze composities, maar liet veel ruimte voor improvisaties. Volgens recensenten biedt het album een perfecte balans tussen toegankelijke modale jazz en hard bop, uitgevoerd door een perfect samenwerkend kwintet.[1] Toch waren de vijf nummers oorspronkelijk niet rond hetzelfde concept geschreven. Het titelnummer Maiden Voyage werd bijvoorbeeld gecomponeerd als achtergrondmuziek voor een televisiereclame. Little One schreef Hancock voor Miles Davis' album E.S.P. (1965) en past qua sfeer bij de rest van het album, al is het oceaanthema minder uitgewerkt.
De jazzstandardsMaiden Voyage en Dolphin Dance bracht Herbie Hancock op een aantal van zijn latere albums opnieuw uit. Nieuwe uitvoeringen van Maiden Voyage en Dolphin Dance verschenen in 1974 op Dedication. In 1981 werd Dolphin Dance opnieuw bewerkt voor het album Herbie Hancock Trio en Maiden Voyage verscheen in 1988 in een nieuwe versie op het album Perfect Machine.