Рассел Лиссак и Келе Окерек впервые познакомились в 1998 году в Эссексе, они учились в разных школах, находящихся в одном районе, но случайно встретившись в 1999 на рок фестивале Reading Festival решили создать группу. Басист Гордон Моакс присоединился к группе благодаря объявлению в журнале NME, а барабанщик Мэтт Тонг стал членом группы после прослушиваний. В начале своего творческого пути группа перебрала множество названий, таких как Union, Superheroes of BMX, The Angel Range, Diet и только после этого, в сентябре 2003 года они остановили свой выбор на названии Bloc Party, означающему так называемые квартирные вечеринки, на которых выступают молодые группы. Bloc Party заявили, что выбор названия никак не связан с Восточным блоком Канадской политической партии Bloc Quebecois.
В ноябре 2003 года трек "The Marshals Are Dead" был включен в CD компиляцию The New Cross, выпущенную Angular Recording Corporation. Затем они выпустили свой дебютный сингл "She's Hearing Voices" на лейбле Trash Aesthetics. Впервые группу заметили, когда в 2003 году Окерек отправившись на концерт группы Franz Ferdinand вручил вокалисту Алексу Карпаносу и диджею британской радиостанции BBC Radio 1 Стиву Ламаку копии сингла "She's Hearing Voices". Ламак впоследствии поставил этот трек на своем радио-шоу, назвав его гениальным и предложил Bloc Party выступить живьем в эфире BBC Radio 1. Позже на лейбле Moshi Moshi Records выходит из пластинка, состоящиая из двух треков "Banquet/Staying Fat", а в апреле 2004 они начинают сотрудничать с независимым лейблом Wichita Recordings.