Steve Vantsis, who was Fish's permanent bassist from the Sunsets on Empire tour (1997) until 2008, was the main writing partner on this album (a role previously held by, among others, Mickey Simmonds, Steven Wilson, John Wesley and Bruce Watson).

Most lyrics deal with, or are at least implicitly in reference to, Fish's failed relationship with Mostly Autumn singer Heather Findlay who left him in 2007, cancelling their scheduled wedding.

The title 13th Star originally referred to her as being the 13th female significant other in Fish's life, but ended up as a metaphor for an (unknown) future relationship.

By contrast, the artwork for 13th Star, spreading across three sides a fold-out digipak and the booklet, marked a return to Wilkinson's hallmark airbrush style that had been a characteristic feature of the Fish-era Marillion gatefold covers as well as Fish's first solo album Vigil in a Wilderness of Mirrors (1990).

The image of the "Dark Angel" navigating his boat from the booklet's front cover illustrates the style and atmosphere of the artwork for this album.

In addition to focusing on the 13th Star material, the tour celebrated the 20th anniversary of Clutching at Straws (Fish's last album with Marillion), and so most of the set list was drawn from these two releases.