Voor de opname van Olé Coltrane werkte Coltrane samen met twee muzikanten uit de Africa/Brass-sessie, namelijk Art Davis (contrabas) en Freddie Hubbard (trompet). Olé Coltrane was het laatste album dat John Coltrane onder Atlantic Records uitbracht. Twee dagen voor de opname van Olé Coltrane was John Coltrane begonnen met zijn eerste opnamesessies voor zijn nieuwe label, Impulse! Records.
Mogelijk kreeg Coltrane belangstelling voor Spaanse muziek door het album Sketches of Spain dat Miles Davis in 1960 uitbracht. De structuur en melodie van het nummer Olé is afgeleid van het Spaanse volkslied El Vito. De overige nummers, Dahomey Dance en Aisha, hebben Afrikaanse titels, maar zijn ook beïnvloed door Spaanse muziek.