After graduating high school, Gordon signed to Liberty Records sister label Patriot Records. There, he released his debut album I Need a Break on February 7, 1995. The album produced the single "The Blue Pages," which spent three weeks on the Billboard country charts, peaking at No. 68.Billboard gave the album a positive review, saying that its opening track "may leave you with the impression that Gordon is yet another honky-tonk pretender," but considered the other tracks to be strongly written. In January 1999, Gordon and Bryan Austin, also a former Patriot Records recording artist, founded a band called Phoenix.