В начале 2001 года КАТЮША (вместе с ВРАГАМИ, ТОРБОЙ-НА-КРУЧЕ и др.) выступила на прослушиваниях шведской компании «Polarvox» в «Голливудских ночах» и даже пробилась в финал конкурса. Першин отыграл с ними до конца апреля, после чего ушел к Курылеву, а потом вообще покинул рок-н-ролл. Его место занял Алексей Мещеряков, еще один сосед по репетиционной базе из группы АНДРОИД.
Весной и летом они играли на полуфинале и гала-концерте первого фестиваля «Окна Открой!», обратив на себя внимание самой широкой аудитории и собрав букет восторженных откликов. Осенью АНТИ, КАТЮШУ и АНДРОИД попросили с их репетиционной площадки, по причине чего в работе всех трех групп наступил незапланированный перерыв.
В феврале-марте 2002 года звукорежиссер студии «Добролет» Константин Никулин записал дебютный альбом КАТЮШИ «Чужое счастье». Четверке музыкантов в этом помогли трубач DDT Иван Васильев и клавишница ТАНКОВ Лиза Андреева, которая после этого на время присоединилась к группе. В мае КАТЮША опять участвовала в «Окнах», но дошла только до полуфинала. Летом они играли на фестивале «Пушкин Drive», а в декабре на «Рок-наводнении» в «Порту».
К этому времени в дискографии группы появились первые диски: в сентябре «Manchester Files» оперативно напечатал тираж «Чужого счастья», а в декабре переиздал его в своей серии «Manchester Exclusive» коллекционным тиражом с автографами музыкантов. Альбом был презентован в клубе «Red».
Группа продолжала интенсивно концертировать по клубам и сочинять новый материал, однако возможности записать и издать его ей не представлялось. Летом 2003 года КАТЮША сделала демо-запись двух песен, которые заинтересовали музыкантов группы ДВА САМОЛЕТА. В то время они только что открыли свою студию «2S Records» и искали для нее потенциальных клиентов.
24 октября 2003 года звукорежиссеры Алексей Тополов (экс-БИТТЕ ДРИТТЕ) и Игорь Корюков приступили к записи второго альбома КАТЮШИ «Понарошку». В конце следующего января сингл с тремя песнями из него был представлен группой на концерте в «Молоке»; позднее в том же году силами САМОЛЕТОВ был издан и сам альбом. В его записи участвовали Лиза Андреева, тромбонист Василий «Васо» Савин (ЛЕНИНГРАД, BILLY’S BAND) и другие гости. Помимо одиннадцати новых песен группы в альбом вошла и «Gangsterito», шуточная кавер-версия песенки гангстеров из мультфильма «Приключения капитана Врунгеля».
Все эти годы ритм-секция КАТЮШИ регулярно играла «на стороне»: Мещеряков после распада АНДРОИДА помогал БАОБАБАМ и – вместе с Куниным – состоял в группе МОРЕ И КОРАБЛИ; помимо того, летом 2001‑го Кунин сотрудничал с АНТИ. Однако в конце 2004 года, после пяти лет интенсивной работы и двух альбомов, в группе разразился кризис: ее покинул Рома Алексеев. Почти одновременно Мещерякова пригласили в СПЛИН, где он заменил Сергея Наветного, а Кунин в начале следующего года стал участником PEP-SEE, а чуть позже – ПОЛЮСОВ. Одно из последних выступлений этого состава состоялось в начале декабря на телеканале «СТО».
В марте 2005 года Шевченко начал набирать новый состав КАТЮШИ, в котором к середине года собрались бывшие участники групп ПРОРВА и БАОБАБЫ Дмитрий «Гриня» Гриднев (гитара), Николай «Колючий» Ерыкалов (бас) и барабанщик ВРАГОВ Сергей «Егазеба» Кивин. Помимо того, время от времени Шевченко с одной гитарой представлял свои песни в клубах «Молоко», «Fish Fabrique» и т. д.
