Lelybus was de naam van het OV-concept van Connexxion voor de gemeente Lelystad. De gemeente, op het moment van aanbesteden nog een VOC-gemeente, verleende de concessie voor een periode van 6 jaar (van 1 januari 2004 tot 31 december 2009). Deze concessie is vervolgens verlengd tot en met 3 september 2011. Vanaf 4 september 2011 is de concessie verleend als Lelystad geeft lucht aan Arriva.
Connexxion heeft de openbare aanbesteding in 2003 weten te winnen door nieuwe lagevloerbussen in te zetten, op rustiger tijden 8-persoons taxibusjes in te zetten en de frequentie te verhogen van 2 naar 4 keer per uur, maar dan wel voortaan in één richting in plaats van lussen in twee richtingen (wat bij elkaar ook 4x/uur was). Bij de bushaltes werd door het Dynamisch Reiziger Informatie-Systeem (DRIS) weergegeven hoeveel minuten het zou duren voordat de volgende bus bij de halte zou arriveren. Al snel bleek dat dit systeem slecht functioneerde en steeds meer van deze palen werden uitgeschakeld. De lijnnummers zijn vervangen door lijnletters (A t/m F).
Bij de start van Lelybus werden in de vroege en late, rustige uren de meeste lijnen gereden door 8-persoons taxibusjes. Dit leek toen een logische keuze, omdat stadslijn 8 naar de Landstrekenwijk al jaren werd gereden door eenzelfde taxibus. Ook werden de streeklijnen 150 naar Enkhuizen en 154 naar Swifterbant op rustige tijden met taxibusjes gereden. Vanaf de start van de nieuwe dienstregeling (waarbij lijn 8 lijn C werd) reden de buschauffeurs op deze voertuigen, maar al snel bleek dat dit te onpraktisch was en werd de divisie Connexxion Taxi Services (CTS) ingeschakeld. Taxichauffeurs reden met een eigen dienstregeling op rustige tijden; de grote bussen reden op drukkere lijnen en tijden. Meermalen is de dienstregeling aangepast omdat bleek dat de taxibusjes de aantallen passagiers niet aankonden; het gebeurde regelmatig dat de busjes vol waren terwijl er nog passagiers op de haltes stonden. Omdat deze taxibusjes niet meer dan 8 personen mogen vervoeren en de capaciteitsproblemen bleven voortduren, is per 26 augustus 2007 de stadsdienst volledig overgeschakeld naar 'grote' bussen.
In juli 2009 is het logo Lelybus op de bussen vervangen door de huisstijl 'Lelystad geeft lucht'. Deze huisstijl is in doorontwikkelde vorm ingezet sinds Arriva op 4 september 2011 de stadsdienst is gaan rijden.