Уход Кузьмина был делом времени. Он произошел во время осеннего тура 91-го года. Этому событию предшествовал «случай в Одессе», когда подвыпивший Кузьмин попытался провести в гримерку мимо ОМОНа барышень из кабака. «Кто такой? Чего прешься в гримерку?» — спросили омоновцы, на что Кузьмин лихо ответил: «Да вы что —..? Я — Кузьмин!!!» Ему почему-то тут же больно ударили по почкам, приговаривая: «Мы шо, в Одессе, Кузьмина не знаем?!».

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

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

Воеводин оказался очень порядочным человеком. «Он был и администратором, и завхозом, и всем, кем только возможно», — вспоминает Бутусов. «Воеводин был для нас всем на свете — отцом, братом, другом, — говорит Копылов, — Он постоянно мотался с нами по всем концертам, таскал на себе барабаны и охранял инструменты. Когда мы голодные поздно вечером приезжали в другой город, Воеводин чуть ли не из-под земли находил для нас еду.» Вскоре Воеводин вполне освоился в премудростях директорской деятельности, и в ближайшие три года проблем с «юридическим фасадом» у группы, как правило, не возникало.

Летом 91-го года администраторы «Наутилуса» договорились с московской студией «Видеофильм» о записи нового альбома, которую планировалось начать в конце осени. Времени оставалось немного, и группа решила сделать черновую версию записи (т. н. «предвариловку») в студии на Фонтанке.

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

В начале лета группа отыграла в Ленинграде концерт, приуроченный к выходу диска «Родившийся в эту ночь», а затем, сознательно отказавшись от всех дальнейших выступлений, сосредоточила силы на создании «Чужой земли». На одну из репетиций Бутусов принес наброски композиции «На берегу безымянной реки» и, показав ее под гитару, сказал: «В идеале она должна быть тропической. Теплой. Хорошей теплой песней.» Музыканты, не сговариваясь, вспомнили о ламбаде. Белкин тут же сочинил симпатичное гитарное соло, и буквально через пару часов песня была готова.

Особенно удачно получилась конечная аранжировка «Прогулок по воде». «Наконец-то нам удалось разложить партии всех трех гитар по своим местам, благодаря чему в музыке резко поубавилось „смурятины“, так сильно переполнявшей „Наугад“», — резюмировал Копылов. В свою очередь Олег Сакмаров считает, что очевидный прогресс в создании нового саунда группы произошел благодаря взаимопониманию, наконец-то возникшему между Беляевым и Белкиным: «Дело в том, что Белкин по своей натуре — упертый рок-н-ролльщик, воспитанный на группах типа „Led Zeppelin“, а Беляев внимательно следил за тем, что происходит в современном музыкальном мире и старается играть конструктивную гитарную музыку конца восьмидесятых. Их совместные „поиски истины“ нередко сопровождались дикими криками, но именно подобные надрывы стали давать классные результаты».

К середине ноября группа завершила сведение «предвариловки», сыграв два концерта с «ДДТ» перед переполненным залом Спортивно-Концертного Комплекса, и отправилась в Москву записывать альбом.

Строго говоря, запись на «Видеофильме» продолжалась с декабря 91-го по февраль 92-го года. С точки зрения Алика Потапкина, на ее не совсем удачный конечный результат сильно повлияло досадное происшествие, случившееся с его барабанами. Дело в том, что после осенних концертов в Новосибирске сотрудники «Аэрофлота» по ошибке загрузили часть багажа ленинградского рейса в самолет, который улетал в Ташкент. Среди этого багажа оказались и потапкинские барабаны. Через несколько месяцев они нашлись, но в Москву Алик приехал без собственных барабанов и весь альбом отстучал на электронных плашках «Simmons», стоявших в студии «Видеофильма». «Первые две недели мы с Полковником только тем и занимались, что отстраивали барабаны, — вспоминает Алик. — Я больше мучился, чем играл, и к концу работы из меня уже были выжаты все соки. На предварительной записи на Фонтанке мы использовали живые барабаны, которые сохраняли эмоции, настроение и драйв. Звук электронных барабанов убил все это.»

Одним из важных моментов при подготовке альбома явилось желание Бутусова вернуться в отдельных фрагментах к клавишному звуку. В отсутствие Могилевского все клавишные партии написал Потапкин — на синтезаторе, одолженном у Андрея Муратова из «ДДТ». Он набросал эскизы фортепьянных проигрышей в «Иване Человекове», «Чужой земле» и «Прогулках по воде». Он же сыграл их и на альбоме, наложив партию клавиш в самом конце, — даже после записи вокала. Это были первые студийные эксперименты Потапкина не в качестве барабанщика. Постепенно он становится вторым музыкальным центром «Наутилуса». Во что это всё выльется, показали дальнейшие события, которые не заставили себя долго ждать.

Окончательно запись «Чужой земли» была завершена в самом начале февраля. В это же время был подготовлен макет обложки, сделанный известным свердловским художником Александром Коротичем, автором обложки легендарного альбома «15» группы «Урфин Джюс». Из не вполне понятных соображений на пластинке не было указано ни фамилий музыкантов, ни авторов композиций — только названия песен.

Отдав матрицу альбома на «Русский диск», группа практически сразу отправилась обкатывать программу. Уже в середине февраля «Наутилус» дал три концерта в Свердловске, отмеченных появлением Могилевского с соло на саксофоне в «Прощальном письме», а также забавными рецензиями в местной прессе с настойчивыми резюме о том, что «концерт стоил этих денег». Дальнейшие события развивались следующим образом. Как всегда, выпускающая пластинку фирма срывала оговоренные сроки выхода, и «Наутилус» был вынужден самостоятельно заявлять о ее планирующемся существовании. «По возможности мы отдавали новый материал на радио, — вспоминает Бутусов, — и, приезжая на концерты, глупо улыбались, сообщая при этом, что у нас новая программа.» Из наиболее значительных выступлений того времени имеет смысл выделить летний концерт памяти Цоя в Лужниках — в одной компании с «Бригадой С», «ЧайФом» и фантастически сильно сыгравшим тогда «Калиновым Мостом». В тот день в Москве стояла З0-ти градусная жара: в гримерке у музыкантов находился специальный бассейн, а зрителей периодически поливали водой беззлобные солдаты.