Mahal had first visited Mali in 1979, and the title of the album comes from the track "Kulanjan" from the 1970 album of kora music, Ancient Strings, by Toumani Diabaté's father Sidiki Diabaté. Mahal and Toumani Diabaté had first met in 1990, and in 1999, Toumani Diabeté selected six virtuoso Malian musicians and took them to record the album with Mahal in Athens, Georgia.
The album was described by New Statesman as "a rousing set of eclectic grooves, calling on ragtime, barrelhouse blues and even rock'n'roll".
Kulanjan was named album of the year by Folk Roots magazine, and President Barack Obama recommended the album in a survey for the Borders book chain.
Taj Mahal followed the album with a tour accompanied by West African musicians, linking his American blues sound to traditional West African rhythms and tracing the origins of blues to West Africa, Mahal also convinced that Mali's Mande griot (musician) clan were his ancestors.