In 1990, Tabor recorded an album with the folk-rock band The Oyster Band titled "Freedom and Rain". She went on tour with the Oyster Band, and the Rykodisc label published a limited-run promotional live album the following year. Many of her current fans first discovered her through this tour and album with the Oyster Band. In 1992, Elvis Costello wrote "All This Useless Beauty" specifically for Tabor, and she recorded it on "Angel Tiger". Costello did not record it himself until 1996, on his album of the same title.