Willoughby was born in 1960 in South Australia. His father was Kokatha, with relations to the Pitjantjatjara and Warlpiri nations; and his mother was a member of the Mirning people, from the Nullabor Plain. Willoughby grew up at Koonibba, which was a Lutheran mission at the time. When he was 15 years old, he began learning at the Centre for Aboriginal Studies in Music at the University of Adelaide. Here he was introduced to drumming, guitars and Western music. Over the next few years there, he developed an unusual style of music by mixing traditional indigenous music with modern Western music styles, particularly reggae.