В начале 90-х Шнуров был завсегдатаем клуба «TaMtAm», где приобщился к современной музыке, позже был частым гостем в «Десятке» и «Горе», освоил бас-гитару и пару месяцев играл на ней в супергруппе АЛКОРЭПИЦА, которую собрали в «Горе» участники движения «Positive Squad». Помимо того, Шнур работал в рекламном отделе радиостанции «Модерн» и активно интересовался электронной музыкой, создав дуэт УХО ВАН ГОГА, в котором с ним работал Игорь Вдовин. Кроме того, Сергей выпустил несколько самиздатовских сборников стихов, которые без особого успеха предлагал различным печатным изданиям и издательствам.
Опыт, полученный во время работы на радио, вероятно, и подсказал Шнурову идею новой группы: рок-н-ролл был излишне патетичен, эстрада откровенно убога, а шансон апеллировал к среднему возрасту и невысокому интеллекту. Нужны были песни с мелодией и драйвом, при этом обращающиеся к публике на том языке, который она использует в общении между собой. «Сначала мною была придумана концепция, совершенно наглая, а потом уже стали сочиняться песни», – признавался Шнур в одном из первых интервью.
Название ЛЕНИНГРАД, возможно, было придумано как своеобразная антитеза популярной у студенческой молодежи Питера 70-х группе САНКТ-ПЕТЕРБУРГ. На свою первую репетицию ЛЕНИНГРАД собрался 9 января 1997-го, за четыре дня до дебютного концерта, назначенного в «Арт-Клинике» на канун старого Нового года, 13 января. Костяк группы составили Шнуров, бас; Вдовин, вокал, и их знакомые по клубной жизни: Андрей «Антоненыч» Антоненко, баритон-саксофон; барабанщик группы НАТАША (на ее точке ЛЕНИНГРАД и репетировал) Александр «Пузо» Попов; студент музучилища им. Мусоргского Илья «Дракула» Ивашов, туба, и т. д.
Поначалу выступления ЛЕНИНГРАДА имели привкус здорового бардака: состав группы менялся от концерта к концерту, а новые музыканты не всегда точно знали, что от них требуется. Тем не менее изустная молва медленно, но верно разносила информацию о «неформатной» группе по всему городу, и ее аудитория постепенно росла.
Летом 1997 года в ряды ЛЕНИНГРАДА влился известный барабанщик Алексей «Микшер» Калинин (ранее НАРОДНОЕ ОПОЛЧЕНИЕ, БУКВА О, НОЖ ДЛЯ FRAU MULLER и т. д.). В декабре группа подписала первый контракт с недавно открытым лейблом «Шок Records», который взял под свое крыло КИРПИЧЕЙ, POSTCOLOR и еще несколько молодых групп. Следующей весной «Шок» выпустил сборник танцевальной музыки «Диско-диско!», содержавший не особо характерный для ЛЕНИНГРАДА лирический номер «Новый год», который Шнуров исполнил дуэтом с вокалистом группы РЕВОЛЬВЕР (Петрозаводск) Максимом Кошелевым.
Одним из первых потенциал ЛЕНИНГРАДА оценил основатель АУКЦЫОНА Леонид Федоров. В то время у АУКЦЫОНА появилась возможность работать на бывшей студии документальных фильмов (ЛСДФ), и Федоров предложил Шнурову помощь в записи дебютного альбома. Весной – летом 1998-го на ЛСДФ ЛЕНИНГРАД записал альбом «Пуля». В роли продюсера выступил Федоров, духовую секцию группы усилили Роман «Ромеро» Фокин, тенор-саксофон; Александр «Сашко» Привалов, труба, и Василий «Кузнечик» Савин, тромбон. Все трое до этого работали с жанрово близкой группой ТОЛСТЫЙ СИРОТКА.
Осенью 1998 года был снят клип на песню ЛЕНИНГРАДА «Я так люблю тебя» (главную роль в нем сыграла DJ Лена Попова; в качестве режиссера выступил Дмитрий Дмитриев, а оператором был Дмитрий Токин). Клип показывали NBN и другие питерские телеканалы, но на столичном MTV его сочли неформатным.
После нескольких поездок в Москву в компании с АУКЦЫОНОМ группу заметила промоутерская компания «Ы», которая устраивала в Москве концерты АУКЦЫОНА, MARKSCHEIDER KUNST и ряда других исполнителей. «Ы» перекупила контракт у «Шок Records», но выпустить «Пулю» не успела: в августе в стране разразился очередной экономический кризис. Как результат в декабре 1998-го ЛЕНИНГРАД на свои деньги издал альбом на кассетах в количестве пятисот экземпляров: только для продажи в магазине молодежной одежды «Актив».
25 декабря 1998 года ЛЕНИНГРАД дал первый концерт в Москве в ДК им. Горбунова перед тем же АУКЦЫОНОМ. Он был отмечен еще и тем, что на нем отсутствовал Вдовин и к микрофону встал сам Шнуров. В выступлении группы участвовал и Леня Федоров, который играл на гитаре и спел несколько песен.
Лишь к лету 1999-го компания «Ы» сумела собраться с силами и выпустить-таки «Пулю» на компакт-дисках под собственным лэйблом «O.G.I.». По содержанию эта версия альбома отличалась от кассетной, а некоторые названия песен были в спешке перепутаны. Позднее ЛЕНИНГРАД авторизовал первую версию дебютного альбома, а «O.G.I.», издав, помимо этого диска, только макси-сингл Федорова и ВОЛКОВТРИО «Небо напополам», незаметно сошел со сцены. Новым издателем ЛЕНИНГРАДА стала солидная московская компания «Gala Records», предложившая группе контракт на выпуск четырех альбомов.