Si sono formati nel 1966 a Genova come Trolls. I membri orinari del gruppo erano Vittorio De Scalzi, Nico Di Palo, Gianni Belleno, Giorgio D'Adamo e Mauro Chiarugi (che lascerà il gruppo due anni dopo).
Dopo aver aperto i concerti italiani dei Rolling Stones nel 1968 il gruppo assume il nome definitivo di New Trolls. Il primo singolo di successo è Visioni contenuto nello storico album Senza orario senza bandiera i cui testi nascono dalla collaborazione tra Fabrizio De André e il poeta genovese Riccardo Mannerini.
Sono al Festival di Sanremo nel 1969 con Io che ho te. Seguono Davanti agli occhi miei e Una miniera.
Nel 1971 sempre al Festival cantano una canzone di Sergio Endrigo, Una storia poco dopo esce l'album Concerto grosso.
Nel 1979 esce un'altra loro canzone famosissima Quella carezza della sera. L'anno dopo è la volta di Aldebaran.
Dal 1985 in poi seguono una serie di partecipazioni al Festival di Sanremo non sempre memorabili: Faccia di cane (1985), Cielo chiaro (1988), Quelli come noi (1992), Letti (1996) e Alianti liberi (1997).
Nel frattempo Gianni Belleno è stato sostiruito da Alfio Vitanza; nel gruppo entra anche, nel 1995, Roberto Tiranti.
Il 15 Gennaio 1998 Nico Di Palo, ha avuto un brutto incidente automobilistico nei pressi di Arezzo, dopo qualche mese è tornato sul palco con una nuova formazione, "Il Mito New Trolls" costituita da Nico Di Palo, Gianni Belleno, Max Corfini, Ricky Belloni e Andrea Lavelli.
Dal canto suo, Vittorio De Scalzi prosegue con una formazione denominata "La storia dei New Trolls" insieme ad Alfio Vitanza, Roberto Tiranti,Mauro Sposito e Andrea Maddalone.
Le due formazioni sono eredi, quindi, dei gloriosi New Trolls, ed ognuna rivendica la propria "originaltà".
Dal 2000, Belleno esce dal "Mito New Trolls" ed è sotituito da Alessandro Polifrone. Contemporaneamente, esce dal gruppo anche Max Corfini