The Kimtones' first performance was at a recital for the Qomar in Voyager's mess hall in 2376. Unfortunately, the Qomar were so enamored with The Doctor's singing that they only wanted to hear him. The Doctor was forced to join the group, singing "That Old Black Magic" after the Qomar's shouts drowned out the Kimtones' instrumental performance of the song. (VOY: "Virtuoso")
While "Virtuoso" is the only named appearance of the group, its prior existence is implied by a Harry Kim-centered jazz trio at the wedding ceremony of the Silver Blood versions of Tom Paris and B'Elanna Torres in "Course: Oblivion". The many detailed similarities between the "real" Voyager and the Silver BloodVoyager suggests that the trio was not an innovation of the Silver Blood ship, but a copy of something that existed on the real vessel.