Born in Cape Town, Moholo formed The Blue Notes with Chris McGregor, Johnny Dyani, Nikele Moyake, Mongezi Feza and Dudu Pukwana,[2] and emigrated to Europe with them in 1964, eventually settling in London, where he formed part of a South African exile community that made an important contribution to British jazz.

In 1966, he toured Buenos Aires, Argentina, where he performed at the Theatron with Steve Lacy, Johnny Dyani and Enrico Rava and recorded the album The Forest and the Zoo with the same musicians.

He was a member of the Brotherhood of Breath, a big band comprising several South African exiles and leading musicians of the British free jazz scene in the 1970s and is the founder of Viva la Black and The Dedication Orchestra.

He has played with many musicians, including Derek Bailey, Steve Lacy, Evan Parker, Enrico Rava, Roswell Rudd, Irène Schweizer, Cecil Taylor, John Tchicai, Archie Shepp, Peter Brötzmann, Mike Osborne, Keith Tippett, Elton Dean and Harry Miller.

South African promoter Slow Life in March 2017 at the Olympia Bakery in Kalk Bay, Cape Town, produced a show where Moholo performed along with Mark Fransman, Reza Khota, Keenan Ahrends and Brydon Bolton.