Interpol zadebiutowali w marcu 1998 r. w klubie Baby Juniper na Lower East Side w Nowym Jorku. Od 1999 r. grali w takich nowojorskich klubach jak Brownies, Mercury Lounge, Bowery Ballroom i Knitting Factory. Na początku 2000 r. w przyjaznej atmosferze odszedł Greg. Zastąpił go Sam Fogarino, który grał wcześniej w punkowych zespołach. Fogarino zagrał swój pierwszy koncert z zespołem (po tylko jednej próbie) 20 maja 2000 r. w Mercury Lounge.
Przez lata 2000–2001 zespół supportował takie zespoły jak Trail of Dead, Arab Strap i The Delgados.
Krótka trasa koncertowa po Wielkiej Brytanii zaowocowała 18 kwietnia 2001BBC - Radio 1 - Keeping It Peel - Sessions - 2001 sesją w programie radiowym Johna Peela (zob. Peel Sessions) i pozwoliła zespołowi uzyskać znaczną popularność po drugiej stronie Oceanu. W tym czasie światło dzienne ujrzał minialbum Interpol EP, zawierający trzy utwory, z których dwa znalazły się na pełnowymiarowym debiucie. EPka ta pozwoliła na ugruntowanie pozycji zespołu jako nowej nadziei niezależnego rocka.