With the band's profile raised, the search for a new record deal began. Some smaller companies showed interest. They decided to go with an independent Colorado based label, Redstone Records, who'd had some successes in the smooth jazz genre. "Messenger" was recorded in Denver and Boulder and was released in September 1994. Bartley had been stockpiling songs for ten years for just this opportunity. Bil Hopkins' song "Say It's Over" (written with Mark Oblinger) and Steve Manshel's "Innocent Victim" also appeared on the CD. Mark Andes and Richie Furay made guest appearances on the album and Jim Mason returned to the producer's chair. "Messenger" was much more diverse than anything the band had released to date with the usual love songs and ballads, but there were also songs about child abuse, environmental catastrophe and even sexual abuse/rape in the chilling "No Means No". The first single, "Love Find A Way", received some minor play on some stations, but Redstone didn't have the distribution clout to get the CD into all stores, so overall sales were disappointing.