Die Gesellschaft wurde am 17. Dezember 2002 als Kobe Airlines (神戸航空Kōbe Kōkū) gegründet und sollte ursprünglich am neuen Flughafen Kōbe angesiedelt werden. Im darauf folgenden Jahr wurde die Fluggesellschaft in StarFlyer umbenannt und zog zum Flughafen Kitakyūshū um. Die Farben schwarz und weiß dominieren den Firmenauftritt – von der Farbgestaltung der Flugzeuge, über die Gestaltung der Check-in-Schalter und Lounges bis zum Internetauftritt. Die ursprünglich als Billigfluggesellschaft aufgetretene StarFlyer unterscheidet sich deutlich von bekannten Billigfluggesellschaften wie beispielsweise Ryanair, Easyjet oder Germanwings. Der für bis zu 180 Passagiere in einer Klasse ausgelegte Airbus A320-200 wurde mit nur 144 Ledersitzen bestückt, die allesamt mit LCD-Monitoren ausgestattet sind. Darüber hinaus ist an jedem Sitzplatz eine Steckdose unter anderem zum Betrieb von Notebooks vorhanden. Am Boden bietet StarFlyer ihren Passagieren zudem eine Lounge an. Alle Flugzeuge der Flotte tragen am Heck den Schriftzug „City of Kitakyushu“ oder „Spirit of Kitakyushu“und werben somit für die Stadt im Norden der Insel Kyūshū.
Mit All Nippon Airways ging StarFlyer am 17. August 2005 eine Kooperation ein, die die Betreuung der Flotte und der Besatzungen umfasst.[2]
Das Anfangskapital von 1,822 Milliarden Yen (≈16,2 Millionen Euro) wurde Ende 2005 durch die beteiligten Gesellschaften auf knapp 4 Milliarden Yen (~27,7 Millionen Euro) aufgestockt.[3] Im selben Jahr übernahm Takaaki Hori die Leitung des Unternehmens von Osako Shinobu.
In Kokura wurde am 16. Januar 2006 das Buchungszentrum eröffnet. Bereits nach wenigen Minuten waren die Tickets für die ersten Flüge im Mai ausverkauft. Ein Flugzeug der StarFlyer eröffnete am 8. Februar 2006 den Flughafen Kitakyūshū, der auf einer künstlichen Insel vor der Küste errichtet wurde. 2006 erhielt das Unternehmen für das von der Firma Flower Robotics Inc. entworfene Design den „Good Design Award 2006“.[4]
Nach Auslieferung der ersten drei werksneuen Airbus A320-200 wurde am 16. Mai 2006, drei Monate nach Eröffnung des Flughafens Kitakyūshū, der Flugbetrieb aufgenommen. Die erste Flugverbindung bestand zwischen Kitakyūshū und Tokio-Haneda.
Im Oktober 2018 nahm StarFlyer ihr erstes planmäßiges internationales Ziel auf. Von nun an wird täglich jeweils eine Verbindung von den Flughäfen Chūbu und Kitakyūshuzum Flughafen Taiwan Taoyuan in der Nähe von Taipeh angeboten.[5]