Презентация альбома должна была состояться в государственном концертном зале «Россия» 12 и 13 июня. К этому моменту «Титаник», только-только появившийся в продаже, уже успел попасть в «топ-10», на телевидении замелькал видеоклип «Титаник», сделанный Геннадием Акименко, а фирма «Мороз Рекордз» прямо-таки завалила рынок ранними альбомами группы, выпущенными на кассетах и «компактах». Не менее помпезно прошли и сами концерты. Месхи и Ланда всерьез решили «дать гари», пригласив принять участие в презентации большой детский хор (Самойлов расписал им вокальные партии на три голоса), музыкантов из «Браво», «Машины времени» и т. д. В процессе репетиций много мук было с приглашенным отрядом барабанщиц, у которых присутствовали красивые ноги, но наглухо отсутствовало чувство ритма. «На первом концерте они устроили т-а-к-о-е ш-о-у, — вспоминает Потапкин. — На композиции „Воздух“ барабанщицы вступили вовремя, только в другом темпе. Несмотря на то, что ими дирижировал Самойлов, они „потащили“ всю команду назад. На записи второго концерта слышно, как мы заранее замедлили из-за них темп песни».

Так как Вадик Самойлов имел возможность принять участие в акции, на сцене стояли два гитариста. Часть сольных партий играл Петров, часть Самойлов, а всю остальную программу Вадик и Николай разложили на две гитары. В центре сцены стоял Бутусов — с черной гитарой, одетый во все черное и чем-то смахивающий на Дэвида Бирна.

Само шоу было выстроено следующим образом. Под причудливым огнями световых эффектов группа играла два отделения. В первом исполнялись композиции «Титаника», а во втором — классические хиты периода 86–92 годов. С точки зрения музыкантов, сами концерты получились не вполне равноценными. В отличие от первого концерта, второе выступление «Hay» (с которого записывался компакт-диск «Titanic Live») прошел сравнительно удачно. «Я испытывал состояние наркотического опьянения от реакции зала», — вспоминает Могилевский. «А мне после одного концерта в „России“ нужно неделю ничего не делать, а просто лежать, чтобы выйти из коматозного состояния», — говорит Бутусов. Итоги «российского» концерта были таковы: его большая часть транслировалась «Программой А», а запись одного из концертов вскоре вышла на двойном компакт-диске «Titanic Live». Что же касается чартов, то к концу лета композиция «Тутанхамон» возглавила сразу несколько хит-парадов.

После спокойного и действительно счастливого лета внезапно начались проблемы. Месхи и Ланда настояли на поездке в Берлин на концерт, приуроченный к выводу российских войск из Германии. Пользуясь случаем, директорат «Наутилуса» хотел получить от Министерства Культуры сверхвыгодный договор, но ничего из этой затеи не вышло. Их жестко отодвинули на второй план группа «На-На» и команда Людмилы Зыкиной. Барри Алибасов и народная певица сказали: «Что это еще за мелкие мальчики?»- и сами сняли все сливки. Более того, под вопросом оказался сам факт поездки группы в Германию.

В итоге тандему Месхи-Ланда пришлось несладко, так как во всех средствах массовой информации уже было раструблено об участии «Hay» в этой акции. В самый последний момент вопрос был решен положительно, но только небеса знают, чего это стоило наутилусовскому директорату.

В Берлин группе пришлось лететь на военном самолете с аэродрома в Чкаловске. Это был последний день официального воздушного моста Чкаловск — Шперенберг (российский военный аэропорт под Берлином), поэтому в загранпаспортах музыкантов не сохранилось никаких отметок о пересечении государственной границы. На их пути не встретилось ни таможенников, ни пограничников — кругом царила не поддающаяся описанию неразбериха, и «Наутилус» вместе с «Агатой Кристи» были вынуждены сидеть прямо посреди леса в Шперенберге в ожидании обещанного автобуса. По странной традиции Германия всегда была для «Наутилуса» чем-то вроде Бермудского треугольника, в котором свердловская субмарина с непонятным постоянством сбивалась с истинного пути. Не стал исключением и данный визит.

«Наутилус» выступал перед несколькими тысячами зрителей прямо посреди бывшей Маркс-Энгельс Платц, расположенной невдалеке от рейхстага. Для постороннего наблюдателя вся акция выглядела воплощением концептуального сюрреализма. Концерт открывал хор имени Пятницкого и ансамбль Александрова с актуальным антимилитаристским шлягером «Вставай, страна огромная». Где-то посредине этого бреда на сцене показался «Наутилус» с программой из семи композиций. На десерт была припасена «Гуд бай, Америка», полная аллюзий на текущий момент. Концерт артистов российской эстрады завершали хэдлайнеры в лице группы «На-На» и Людмилы Зыкиной. Под звуки народных мелодий семьи российских офицеров готовились к возвращению на свою историческую родину.

Непродуманная поездка в Германию сильно подорвала доверие Бутусова к своим директорам. В интервью прессе он напрямую заявил, что в Германии группа оказалась по воле менеджеров:

«Я человек … не то чтобы очень принципиальный, но, если я имею с кем-то договоренность, то стараюсь ее соблюдать. Естественно, может наступить момент, когда я, ничего не объясняя, расстанусь, допустим, со своим администратором, который перестанет меня устраивать. Но до той поры я считаю, что должен выполнять свои обязательства».

В это время группа совершала крупный тур по России, в течение которого за лето-осень 94 года «Наутилус» дал около 70 концертов. После нескольких из них Бутусов созвонился с организаторами концертов на местах с целью уточнить гонорары, выплаченные директорату, и сравнить их с гонорарами, полученными музыкантами. Цифры не совпадали. И Бутусов понял, что добрая старая школа киевско-израильского менеджмента помимо плюсов имеет существенные минусы. Уже позднее выяснилось, что Месхи и Ланда снимали деньги со счетов группы в первую очередь для того, чтобы заткнуть финансовые бреши, возникшие после Берлина и презентации в «России». Возможно, их погубило то, что попросту не хватило духа во всем откровенно признаться группе.

Как бы там ни было, в конце 94-го года контракт между «Наутилусом» и его директорами был разорван. Директором группы стал Александр Пономарев, раньше работавший с «Браво» и помогавший «Наутилусу» в организации концертов в «России».

Каторжная работа над «Титаником» и его беспримерная раскрутка в конце концов принесли ощутимые результаты. По итогам 94-го года «Наутилус» получил национальную премию «Овация»- как «лучшая рок-группа», в хит-параде «МК» группа заняла второе место. «Титаник» попал в десятку («8-ым»), а Бутусов и Кормильцев вошли в тройку лучших рок-певцов и рок-поэтов соответственно. К концу года от 35 000 экземпляров компакт-дисков «Титаника» не осталось и следа, а количеству кассет и пиратских перепечаток, разошедшихся по стране, уже давно потерян счет. Жаждущие зрелищ народные массы впитывали в себя песни «Наутилуса» со всех сторон — начиная от FМ-радиостанций и заканчивая телевидением. Сам же «Наутилус» с марта 95-го года надолго залег на дно — на повестке дня стоял вопрос о создании нового альбома группы.

«Мы пытались его очень тщательно спланировать и очень долго все это делали, — вспоминает Бутусов. — Буквально сразу после завершения записи „Титаника“ мы начали готовить новый материал. Было стремление сделать как можно больше песен, чтобы было из чего выбирать. Я писал „рыбы“ практически до Нового года. Потом шла работа с текстами. И почти полгода мы сидели в студии».

После окончательного отбора выяснилось, что альбом будет содержать только пять свежих композиций — «Небо и трава», «Крылья», «Одинокая птица», «Дыхание» и «Живая вода». Большинство остальных песен были написаны еще в период подготовки «Титаника», а композиция «Золотое пятно» создавалась одновременно с «Бриллиантовыми дорогами». Первоначально альбом планировалось назвать «Усталость» — по названию одноименной композиции. Но в последний момент эта песня (впрочем, как и уже записанная «Заноза») в «Крылья» не вошла.