Bandet ble startet av Fredrikstad-musikeren Frode Fivel (gitar, sang) og svenskene Johannes Kanschat (trommer) og Elisabet «Lisa» Lundkvist (vokal). De møtte hverandre på Kunstakademiet i Oslo mot slutten av 90-tallet. De første årene hadde de ingen bassist, og de har aldri hatt noe stort trommesett heller, nærmest bare et utvalg rytmeinstrumenter. Bandets første jobber var på gata i Oslo.
Deres første plateutgivelse var en single på Smalltown Supersound med tittelen «Pussycat»/«African Night» i 1999. I 2001 begynte Alex Kloster-Jensen fra ►The Ricochets på gitar, men trakk han seg ut av bandet i 2004. Hello Goodbye fikk da hjelp av kontrabassisten Lars Borg, som siden har lånt ut hjelpende hender både på plate og på scenen.
Hello Goodbye albumdebuterte i 2002, samme år som de gjorde en fantastisk konsert på Øyafestivalen i Oslo. Album nr. to kom 2004. De har turnert en hel del i utlandet, bl.a. vært supportband for ►Madrugada på en Europa-turné. Frode Fivel utga solo-albumet Patience Will Win i 2003 på Honeymilk.
Heart Attack (Racing Junior, 2002)
Haunted Holiday (Racing Junior, 2004)