В марте этого же года, в рамках эпатажного шоу «Бойцовский клуб», в котором музыканты разных стилевых направлений состязались друг с другом в настоящих боксерских поединках, на ринге сошлись «Король и Шут» и группа «На-На».

В гастрольный список группы, к уже «освоенному» ближнему зарубежью — Украине и Белоруссии, теперь добавились города Казахстана, Молдовы, Прибалтики.

В июне 2003 года в Санкт-Петербурге состоялось открытие «фирменного» рок-клуба — «Старый Дом». «Король и Шут» участвовали в создании и оформлении площадки, в нём же репетировали и часто давали концерты. В «Старом Доме» выступали разномастные российские рок-группы, проходили отборочные туры фестиваля «Окна Открой!», играли британские рокеры Gold Blade и метал-команды из Финляндии. К сожалению, два года спустя клуб был закрыт по финансовым причинам.

При поддержке «НАШЕго Радио» выходит релиз «Попса» под эгидой т. н. «Рок-Группы», в состав которой вошли Юрий Шевчук («ДДТ»), Александр Чернецкий («Разные Люди»), Илья Чёрт («ПилОт») и Алексей Горшенёв («Кукрыниксы»). Лидеры группы «Король и Шут», Горшок и Князь, в рамках релиза участвовали в записи песен «Кошка» и рок-манифеста «Попса» группы «Бригадный Подряд».

В том же году «Король и Шут» впервые дают гастроли в Америке, Израиле и Финляндии.

А 18 декабря, в самом легендарном зале страны — СК «Олимпийский» (Москва) — при полном аншлаге группа отыграла масштабный 3-х часовой концерт, впоследствии изданный на VHS и DVD.

Перемены в середине 2000-х

В начале 2004 года скрипачка Мария Нефедова приняла решение покинуть коллектив в связи с переездом в Америку.

В том же 2004 году «Король и Шут» выпускают свой самый жёсткий по саунду, выдержанный в стилистике хардкора, альбом «Бунт на Корабле», в записи которого приняли участие Александр «Рикошет» Аксёнов («Объект Насмешек») и Евгений «Ай-яй-яй» Федоров («Tequilajazzz»). После выхода «Бунта на корабле» режиссёром Валерием Хаттиным (автором видео «Проклятый старый дом») был снят клип на песню «Месть Гарри».

Директором группы становится Вячеслав Батогов, являющийся также директором группы «АлисА», что, в дальнейшем, способствовало созданию совместных творческих проектов двух коллективов.

В 2005 году на свет появляются сразу два индивидуальных детища фронтменов «Короля и Шута».

Горшок презентует сольный альбом «Я — алкоголик, я — анархист», состоящий из песен панк-группы «Бригадный Подряд» и записанный с целью благотворительной поддержки музыканту Николаю Михайлову. Князь выпускает мелодичный акустический альбом «Любовь негодяя», в работе над которым приняли участие музыканты группы «Аквариум» — Олег Шар и Владимир Кудрявцев, Сергей Янсон из «Хоронько-оркестра», Сергей «Чиж» Чиграков, вокалистка Юлия Худякова, а также скрипач группы Dominia — Дмитрий «Casper» Ришко.

В поддержку обоих альбомов были даны концерты в Москве и Санкт-Петербурге. На песню «Соловьи» из альбома Горшка «Я — алкоголик, я — анархист» был снят клип, за который Михаил Горшенёв в апреле 2006 года получил премию «Fuzz» в категории «Лучшее видео».

В июне MTV приглашает «Король и Шут» в программу «Полный контакт», где их «соперниками» становится группа «Пилот». На федеральном канале ТВЦ проходит показ программы «Кухня. Открытый проект», в которой «Король и Шут» отыграли несколько композиций в акустическом варианте.