The All-Stars were a short-lived English blues combo active in the early-mid 1960s. Originally known as the Cyril Davies (R&B) All-Stars, their later recordings are often credited to the Immediate All-Stars due to their releases on Immediate Records. In 1999, the group reformed as the Carlo Little All-Stars.

The All-Stars were initially formed as a backing band for vocalist and blues harmonica player Cyril Davies after his departure from Alexis Korner's Blues Incorporated in October 1962. The original lineup was tentatively named 'The Cyril Davies Blues Band' and was made up of former members of Screaming Lord Sutch's group, the Savages, including Nicky Hopkins on piano, Carlo Little on drums and Ricky Fenson (aka Rick Brown) on bass. The band also featured Jimmy Page on guitar for a brief period, though he soon backed out to focus on his burgeoning career as a session musician and was replaced by Bernie Watson, another former member of the Savages.

In December 1962, Davies was in competition with Korner to recruit Long John Baldry as a second lead vocalist. Baldry had previously performed with Blues Incorporated while Davies was still a member, with both vocalists being featured on the 1962 album R&B from the Marquee. Following the formation of the All-Stars, Baldry played a few shows with each band before eventually committing to join Davies' camp in January 1963.

Around this time, Davies also added female backing singers to the lineup in the form of South African vocal group the Velvettes (not to be confused with Motown trio, the Velvelettes), who had emigrated to England after touring with the musical stage production King Kong. The Velvettes were initially a quartet made up of Peggy Phango, Hazel Futa, Patience Gcwabe and Eunice Mamsie Mthombeni, though Phango soon departed to pursue a solo career, leaving the rest of the group to join the All-Stars as a trio.

On 27 February, the All-Stars recorded their first single for Pye Records: the original compositions "Country Line Special" and "Chicago Calling", released under the name 'Cyril Davies and His Rhythm and Blues All-Stars'. However, Baldry and the Velvettes are not featured on these recordings.

In May 1963, illness forced the departure of Hopkins as he was hospitalised for several months. Former Blues Incorporated pianist Keith Scott was recruited in his stead, but growing tensions between Davies and the other band members meant that Fenson, Watson and Little each soon left the group to be replaced by bassist Cliff Barton, guitarist Geoff Bradford and drummer Micky Waller.

In August, this lineup recorded the R&B All-Stars' second single for Pye: "Preachin' the Blues", a Robert Johnson cover, and "Sweet Mary", a Lead Belly cover. As with the previous recordings, Baldry and the Velvettes are not featured. Instead, backing vocals for "Preachin' the Blues" are provided by Alex Bradford and Madeline Bell. Towards the end of 1963, Scott and Waller were themselves replaced by the group's final members Johnny Parker and Bob Wackett.

Cyril Davies died on 7 January 1964 of pleurisy and endocarditis. Following this, Pye Records paid tribute to Davies by re-releasing the four tracks he had recorded for them as the EP The Sound of Cyril Davies and His Rhythm and Blues All-Stars.