Malcolm Yelvington came from the area of Covington, Tennessee, some forty miles north of Memphis, born on September 14, 1918 to Frank Yelvington and Sarah Edwards. Covington is a country area, as famous for its Tomato Festival as much as anything else, but back in the 1930s when Malcolm's musical interests were first formed, it was a very country area indeed. The big musical influences back then were the string bands of barn dance radio shows, the popular ballads of the day, Bob Wills' western swing music, and the emerging honky-tonk sounds of Al Dexter or Ernest Tubb. When asked in later years, Malcolm would normally list his musical interests as 1930s and 1940s popular swing and big bands and the country music of Bob Wills and Jimmie Rodgers. Nearer to home, the Swift Jewel Cowboys played jazzy western-swing on Memphis radio every week, while Reece Fleming and Respers Townsend were a famous local duo who recorded blues and ballads for Victor and Decca.
At some point, Malcolm decided that he would try his hand at performing in public. He usually described a show at the Gem Theater in Covington in 1943 as his first public appearance, singing and playing solo acoustic guitar. He had played for years at family events and suchlike, and had formed several alliances with other musicians. One of his neighbours, Charles Yoakum, recalled: "We were both from Tipton County and played music together. We shared a common love of music and Malcolm was the genuine article." Around 1941, Malcolm met and married his wife, Lou Ella, who also encouraged him in his musical ambitions.
Soon after this, Yelvington got together with Reece Fleming, already a veteran recording artist, to put together a small band in Covington with steel guitarist Miles 'Red' Winn, called the Tennesseans. Fleming was the son of William Robert Fleming and Emma Raynor, the last of eight children. He and Respers Townsend had first recorded for Victor in Memphis in May 1930, and over an eight year period they went on to see releases on Bluebird, ARC, and Decca as well. Mostly they made vocal and yodelling duets with Fleming on guitar and Townsend on harmonica. Drawing on blues and hillbilly folk traditions, they sometimes took a salacious approach – I'll Tell You About Women, Bad Reputations, She's Just That Kind, and so on – but mastered a full range of folk and popular songs.
Reece Fleming played both guitar and piano when the newly-formed Tennesseans played club dates on weekends and the occasional theatre or school house. Fleming was married to Lavern West, a good pianist, who often played with the band. One day in 1948 they cut some western-swing demos direct onto an old acetate recording machine owned by Fleming. Unfortunately these very first recordings by Malcolm Yelvington are now lost.
In 1952, the Tennesseans merged with another local band, the Star Rhythm Boys. Their guitarist and leader, Gordon Mashburn, and bass player Jake Ryles joined Yelvington, the Flemings, and Winn in the newly-named outfit, Malcolm Yelvington and the Star Rhythm Boys. The group played wherever they could locally, but now they started a three-year residency at the Clover Club. They also gained a half-hour slot on Covington radio station WKBH on Sunday afternoons, and in 1954 they added a daily show of fifteen minutes. This meant taping a weeks' worth of shows each weekend since most of the band members, apart from the older Flemings, moved to Memphis in the winter of 1954/55 to gain steadier day jobs in the city.