Waltz for Debbie är ett electropop/indiepopband som bildades 1996 av Martin Permer och Annica Lundbäck. De träffades när de båda studerade vid Lunds universitet. Det är framförallt Permer som skriver låtarna.
Gruppen singeldebuterade med 1998 års You & I & Brett & Alice, vilken utgavs 1998 på Stockholm Records. Därefter bytte gruppen skivbolag till Labrador. En andra singel, He Loves Anna, kom ut i juli 1999, och i januari 2000 kom den andra uppföljningen Once Upon a Time vilken även nådde butikerna. Den låg tio veckor på P3:s hitlista. Samtliga tre singlar finns med på deras debutalbum, Gone and Out som släpptes den 13 juni 2000. Tre av bandets låtar, bland annat He loves Anna, finns även med på soundtracket till filmen Fjorton suger.