Majaivana became involved in music through the church his father was a minister of, by singing in the choir. When he was 15, he played drums in a band that became quite popular in his home district of Bulawayo. He went to Harare, shifted gears and took up singing, performing material by such Western artists as Tom Jones and Elvis Presley on the hotel and nightclub circuit. In 1974, he returned to Bulawayo to perform with the Marisha Band. Four years later, he went back to Harare and formed his own band, Jobs Combination, which performed various popular musical idioms. They had several successful singles early on, and their debut album was a big seller. Despite all this, the band broke up shortly thereafter, and Majaivana sang with the Real Sounds for about two months.
The turning point in his career came when he joined the Zulus, a band from Victoria Falls which featured two of his brothers. Finally having a stable base from which to work, Majaivana and his band released an album of traditional folk songs, Salanini Zinini, that he and his brothers had learned from their mother in 1984. Since then, he has progressed completely away from his former Western influences, and his popularity continues to build; his first international album was released in 1990.