Nonstop entstand Anfang des Jahres 2001 aus der portugiesischen Version des Gesangswettbewerbs Popstars, ausgestrahlt vom Sender SIC. Die Band bestand anfänglich aus 5 Sängerinnen. Ihre Besetzung wurde am 4. April 2001 erstmals bekanntgegeben.
Ihr erstes Album nonstop erschien am 16. Juli 2001 und erreichte Gold-Status. Schon nach sechs Monaten verließ Fátima Sousa im Januar 2002 die Band. Im Jahr 2004 gelang den vier verbliebenen Sängerinnen ein Comeback. Ihr zweites Album Tudo Vai Mudar erschien am 5. Mai 2004.
Am 10. März 2006 gewann Nonstop mit Coisas de nada die portugiesische Vorentscheidung zum Eurovision Song Contest, das Festival da Canção in Lissabon.[1] Beim europäischen Semi-Finale am 18. Mai 2006 in Athen reichte es bei 23 Teilnehmern nur für einen enttäuschenden 19. Platz.