I Midtown nascono negli ultimi mesi del 1998 ad opera di tre ragazzi di New Brunswick, nel New Jersey, Stati Uniti, che frequentano la Rutgers University e si conoscono in quanto tutti fanno già parte di band locali che hanno suonato insieme alcune volte. I tre, Gabe Saporta, Tyler Rann e Rob Hitt, credono però che i loro gruppi non possano avere successo perché mancano di alcuni dinamismi interni, e pertanto vogliono creare una band fondata sull'amicizia. Al gruppo, in cui Rob suona la batteria, Tyler la chitarra e Gabe il basso, mentre gli ultimi due si dividono il cantato, si aggiunge qualche mese più tardi Heath Saraceno come secondo chitarrista e terzo cantante, con il quale vengono registrati nel dicembre dello stesso anno i primi cinque brani, che vanno a comporre il primo demo. Nel gennaio del '99 ha luogo il primo concerto, in una cantina di New Brunswick, davanti a 40 persone. Poco dopo, in febbraio, il demo viene rilasciato sottoforma di un EP intitolato "The Sacrifice Of Life" dalla Pinball Records, un'etichetta indipendente del New Jersey. I Midtown iniziano così a suonare nei week-end in vari locali della costa est statunitense, mentre nel frattempo il loro EP arriva alla Drive-Thru Records, importante etichetta californiana, che decide di concedere loro un contratto: il gruppo si reca così al Doug Messenger Studios di North Hollywood, in California, per registrare, con Mark Trombino (già produttore di band quali Blink 182 e Jimmy Eat World), il primo full-length. Mentre l'album è in produzione, i Midtown tornano alla Rutgers per frequentare il loro ultimo semestre (a fine '99), in quanto nel gennaio del 2000 decidono di diventare un gruppo a tempo pieno. L'album, "Save The World Lose The Girl", il cui titolo deriva da quello di una puntata di Spiderman, esce in febbraio, e la band parte per un tour statunitense, durante il quale ha però un incidente col suo van: ad un certo punto un cervo attraversa la strada e, nel tentativo di evitarlo, il pulmino finisce fuori strada. Stacy, una ragazza amica dei Midtown che vende per loro il merchandise del gruppo in tour, viene catapultata fuori dal finestrino, riportando delle serie ferite. La ragazza, che ha appena finito il college e ancora non lavora, però non ha alcuna assicurazione (negli Stati Uniti le leggi assicurative sono diverse che in Europa), e pertanto deve pagare le spese mediche di tasca sua (anche il sistema sanitario è diverso rispetto a quello italiano ed europeo). I Reel Big Fish ed i Catch 22, le band con cui i Midtown sono in tour, prestano al gruppo i loro equipaggiamenti ed anche un van, permettendo così al tour di proseguire. Nel frattempo i Midtown aprono un conto corrente sul quale chiedono ai fans (principalmente tramite il sito ufficiale) di fare delle offerte per Stacy, ed organizzano due show di beneficenza per raccogliere altro denaro, al quale partecipano anche Saves The Day, Goldfinger e Movielife. La risposta dei fans è notevole (arrivano offerte anche da Europa e Giappone, dove il gruppo non è ancora mai stato in tour), e perciò viene raccolta una buona somma. In settembre partono poi per il loro primo tour in Giappone, mentre in novembre l'album esce anche in Europa grazie alla Burning Heart Records che lo ha ottenuto in licenza. Nel frattempo i Midtown tornano negli U.S.A. per fare un tour statunitense di supporto agli A New Found Glory, rilasciando anche uno split con la band floridense per la Drive-Thru. Agli inizi del 2001 il gruppo, mai stanco dei suonare (ha effettuato in un anno più di 250 date) parte per il suo primo tour europeo, che dura sette settimane, suonando nelle date tedesche di supporto ai Donots (band molto apprezzata in Germania), prima di tornare negli Stati Uniti per il primo vero tour nazionale come headliner. Intanto, in marzo, la Bushido Records (una piccola etichetta tedesca) e la Stereodrive! Records in collaborazione rilasciano, in 500 copie, uno split dei Midtown coi Donots (che contiene anche un'inedito), mentre in giugno esce uno split con i Millencolin (contenente due inediti), edito dalla Golf Records. Poco dopo i Midtown partecipano al Vans Warped Tour annuale, prima di suonare per due settimane con i Blink 182 durante il loro tour estivo, spesso davanti anche a 15.000 persone. La band intanto ha firmato con la MCA Records, una major parte del gruppo della Universal Music Group, con cui la Drive-Thru è affiliata (nel senso che la MCA ha diritto di precedenza su ogni altra etichetta di mettere sotto contratto una band della Drive-Thru). I Midtown si recano così in studio ancora con Mark Trombino per registrare dei nuovi brani, composti per la maggior parte con una chitarra acustica nel retro del loro pulmino mentre erano in tour, visto che dal rilascio di "Save The World Lose The Girl" la band non è stata a casa per più di qualche settimana. Il nuovo album viene registrato in parte al Larrabee East di Los Angeles ed in parte al Media Vortex Studios di Burbank, entrambi in California, e vede la partecipazione ai cori di Vinnie Caruana, cantante dei Movielife (ed include anche gli inediti inclusi negli split coi Millencolin e coi Donots). L'album, "Living Well Is The Best Revenge", esce nell'aprile del 2002 edito in collaborazione dalla Drive-Thru e dalla MCA, quando ormai "Save the World Lose The Girl" ha venduto 50.000 copie. Il gruppo partecipa così nuovamente al Warped Tour annuale, mentre il nuovo full-length, a sei mesi della sua uscita, ha già superato i 75.000 esemplari venduti, aiutato anche dal video girato per "Like A Movie", che viene passato anche da MTV 2.