Maurizio Vinci e Alessandro Cimarosti sono due ragazzi di due paesini lombardi che, sebbene si trovino in province differenti (quello di Maurizio è infatti in provincia di Brescia mentre quello di Alessandro in quella di Mantova), sono molto vicini tra loro, distando appena una decina di chilometri l'uno dall'altro. I due ragazzi nel luglio del 1999 decidono di dare vita ad una band, interpretando rispettivamente il ruolo di batterista e cantante, e per completare la formazione chiamano a partecipare anche i loro amici Nicola "Peco" Pecorari e Fano alle chitarre e Patrick Menozzi al basso. Il gruppo decide di darsi nome L'Invasione Degli Omini Verdi perché lo ritengono un nome adatto ad una band di hardcore melodico in quanto, quando la gente vede qualcosa di diverso, questo viene classificato come "alieno". Ma presto Fano se ne va e Alessandro decide perciò di iniziare a suonare anche la chitarra oltre che cantare, e così il gruppo registra come quartetto agli inizi del 2000 il suo primo demo omonimo, che permette loro di avere maggiori possibilità di suonare in giro, anche con band piuttosto conosciute nella scena punk italiana. E proprio ad uno di questi concerti, insieme ai Derozer, la band conosce Alberto e Stefano della P.O.T.A. Records, i quali offrono loro una collaborazione che porta nel luglio del 2001 L'Invasione Degli Omini Verdi ad entrare al Blue Train's Studio di Mira, in provincia di Venezia, per registrare un primo vero disco: nasce così "Veniamo In Pace", che viene rilasciato dalla P.O.T.A. in novembre. L'album vende molto bene, esaurendo le prime 1.000 copie stampate in poco più di sei mesi dall'uscita, anche grazie ad un tour di quasi 40 date che li ha portati anche a suonare un concerto in Croazia. Nel giugno del 2002 Peco decide però di lasciare L'Invasione Degli Omini Verdi per dedicarsi interamente all'altro suo gruppo, le Officinalchemike: poco dopo viene sostituito con Giovanni "Giò" Bottoglia, e con lui la band in luglio suona ad un festival a cui partecipano anche i Vandals. Intanto "Veniamo In Pace" è ormai prossimo alle 1.500 copie vendute, ma il gruppo continua l'attività compositiva entrando nel febbraio del 2003 al Digitube Studio di Mantova per registrare un nuovo album, "Non E' Un Gioco", che viene rilasciato in maggio dalla Linfa Records.