Inglise indierocki bändide Travis ja Coldplay edu 90-ndate lõpus innustas plaadifirmasid soosima just sellise suuna nooremaid tulijaid. Üheks nendest oli 2000 aastal ühinenud Starsailor, kes pärines Lancashire’st UK-s. Bändi moodustasid neli noort meest: James Walsh (laul, kitarr), James Stelfox (bass), Ben Byrne (trummid) ja Barry Westhead (klahvpillid). Nimi Starsailor pärines aga USA laulja Tim Buckley samanimelise albumi järgi.

Esimest korda esineti aprillis 2000 ning juba mõned kuud hiljem oli poistel olemas plaadileping EMI Pharlaphone Recordsiga. Ekstensiivne raadiote tulistamine tõstis nende 2001 märtsis ilmunud Fever EP kohe UK Top 20-sse. Järgnesid ridamisi edukad singlid "Good Souls" ja "Alcoholic" ning debüütalbum ”Love Is Here” anti välja 8.oktoobril 2001. Paljukiidetud albumilt ilmus singlina veel lugu ”Fever”.

Järgmise albumi lindistamine viis bändi pendeldama Ameerika ja Inglismaa vahele, sest kaasati omaaegne poplegend Phil Spector. Tema mõjutusi on kõvasti tunda suurtes raadiolemmikutes ”Silence Is Easy” ja "White Dove". Starsailor teine album ”Silence Is Easy” ilmus 15.septembril 2003. Viimane hittsingel oli "Four to the Floor", mille remiksid hullutasid isegi tantsusaale 2004 aasta talvel ning kokku andsid ansambli kaks esimest albumit lausa üheksa UK Topp 40 singlit.

Laulja-kitarrist James Walshi poolt tüüritud Starsailor esitleb “On The Otherside” albumil ansambli kontserditelt tuntud saundi. Parlophone’ilt 17.oktoobril 2005 ilmunud kolmas Starsailori album sisaldab mõnusaid kitarririffe, Hammond soundiga vürtsitatud refrääne ja Walshi kaunisti värisevat häält. Albumi parimateks paladeks võib pidada esimest singlit “In the Crossfire”, “Way Back Home”, “Keep Us Together” ning vihane blues "I Don't Know". Limited edition sisaldab DVD-d, millel “In The Crossfire” video, live videod lauludest “In My Blood”, “Tie Up My Hands” ja “Silence Is Easy”.

Teine singel oli ”This Time” 23.jaanuaril 2006 ning head rocki pakkus ansambel ka 08.mail 2006 ilmunud singliga "Keep Us Together".

Ansambli neljas stuudioalbum "All The Plans" tuli välja 02.märtsil 2009 ning kõigile fännidele kes plaadi ette tellisid kingiti tasuta allalaaditav EP. Plaadi esimeseks singliks on "Tell Me It's Not Over", mille promovideo autoriks Dan Sully. Bänd on peale eelmise albumi ilmumist saanud küpsemaks ja seda on ka nende lugudest tunda. Steve Osbournei produtseeritud ”All The Plans” albumil moodustavad James Walshi õrnad tõlgendused ja kaunid meloodilised lood tugeva vundamendi õnnestunud tervikule.

13.novembrist 2009 on ansambel puhkusel.

21.jaanuaril 2014 andis laulja James Walsh teada oma sooloplaadist "Turning Point", mis ilmub 7.aprillil. Plaadil kõlab 11 lugu.

Starsailor osales novembrist 2014 ansambli James UK tuuril ning suvel ollakse tuuril USA-s.

Oktoobris 2015 toimus UK suurlinnades Good Souls tuur. Selleks puhuks anti välja 17-looline kogumikalbum "Good Souls: The Greatest Hits". 18.septembril ilmunud plaadil kõlab lisaks kaks uut lugu - "Give Up The Ghost" ja "Hold On".

1.septembril 2017 ilmus ansamblilt album "All This Life", millel kõlab 11 lugu. Esimese näitena toodi esile lugu "Listen To Your Heart" ning 21.juulil tuli välja singel "All This Life". Viimase video avaldati 14.augustil.

10.detsembril 2021 andis Starsailor 20-ks aastapäevaks välja 2001 aasta albumist "Love Is Here" deluxe versiooni. Lisamaterjaliga plaadile salvestati 5 lugu uuesti üles.

Starsailor uus album "Where The Wild Things Grow" tuli 22.märtsil 2024 ning sisaldas 11 lugu. 27.oktoobril 2023 esitleti nimiloo videot. Plaadil aitavad kitarrisoolodega Tony “Doggen” Foster (Rick McNamara) ning Andy Dunlop (Travis), taustalauljaks on Lucy Joules (Sam Smith). Lood produtseeris Rick McNamara. 24.novembril esitleti lugu "Heavyweight".