Первой записью группы был EP Demo Tape с тремя песнями, выпущенный в 1998 году на самиздатовских кассетах; их следующий мини-альбом 2000 года, Fukd ID #3, появился уже под лейблом — Chemikal Underground. После его выхода в группе произошёл раскол: из-за «непреодолимых творческих разногласий» Interpol покинул барабанщик Грег Друди (как заявляют музыканты, Грег с тех пор не то чтобы оставался в плохих отношениях с ними, их пути просто разошлись). Группе потребовался новый барабанщик, но он нашёлся быстро: Дэниэл Кесслер позвал Сэма Фогарино — работника музыкального магазина, который Interpol неоднократно посещал.

Как только Interpol набрал достаточно средств для записи первого полноценного альбома, они обратились к издательству Matador Records, работающему с инди-рок музыкой, и послали имеющиеся у них записи его сопредседателю Джерарду Кослою. Он оценил их творчество, но ответил, что на тот момент издательство пока не могло принять их. После длившейся целый год переписки группа решила отправить туда несколько самиздатовских демо, которые сильно понравились Кослою, а также его партнёру Крису Ломбарди. Вследствие этому, 4 июня 2002 Matador Records выпустила, для начала, EP Interpol, содержащий в себе песни «PDA», «NYC» и «Specialist». Когда он получил положительную критику, Interpol приступили к записи своего дебютного альбома Turn on the Bright Lights, который был издан 19 августа 2002 года. Turn on the Bright Lights принёс группе большой успех, завоевав 59-е место в «100 Лучших Альбомов Десятилетия» журнала Rolling Stone и 1-е в «Топ-50 Альбомов 2002» сайта Pitchfork Media, где творчество Interpol’а сравнивали с такими пост-панк-группами прошлых десятилетий как Joy Division, Echo & the Bunnymen и Mission of Burma.

В конце 2003 года Interpol, после пришедшей к нему славы, вновь собрался в Matador Records для записи своего второго альбома. Этот альбом, названный Antics и выпущенный 28 сентября 2004 года, утвердил музыкантов больше в инди-рок жанре, чем пост-панке, но поддержал популярность группы: он разошёлся в около 488 000 экземпляров в США и породил такие хиты Interpol’а как «Evil», «C’mere» и «Slow Hands». После выхода альбома Interpol отправился в мировой концертный тур — самый большой на тот момент, по длительности и местах выступлений. Длительность тура составила около 18 месяцев, в течение которых Interpol’у довелось играть на сцене с группами U2 и The Cure, а также записать сингл «Direction» для саундтрека к сериалу «Клиент всегда мёртв».

Переход к Capitol Records

О следующем, третьем альбоме Interpol’а впервые сообщил вокалист Пол Бэнкс на официальном сайте группы: после некоторого отдыха от рок-деятельности музыканты собрались вновь и проработали шесть месяцев над новым материалом. Однако, их контракт с лейблом Matador Records истёк, и группе нужно было искать новое издательство. Поначалу ходили слухи, что им станет Interscope Records, но барабанщик Сэм Фогарино опроверг их, назвав это чистым предположением. 14 августа 2006 года на своём официальном сайте группа сообщила, что их новый альбом будет выпущен лейблом Capitol Records; 1 сентября это же подтвердило издательство Matador Records.