В 1828 году за добросовестное выполнение заданий Пахтусова произвели в прапорщики, а три года спустя — в подпоручики корпуса флотских штурманов.
Офицера-гидрографа поздравляли друзья, однако он искренно говорил, что был бы больше рад, если бы приняли его проект изучения восточного побережья Новой Земли, посланный им в Петербург в Гидрографический департамент. Проект одобрили, но… отложили до лучших времен по причине «отсутствия потребных ассигнований». И это несмотря на то, что экспедиция должна была обойтись неслыханно дешево, требовалось всего несколько тысяч рублей. Гидрографический департамент, очевидно, побоялся отпустить средства на осуществление проекта никому не ведомого штурмана, да и вообще сомневался в возможности проникнуть к восточному побережью Новой Земли. Но Пахтусов не сдавался. Он решил организовать экспедицию на частные средства и стал упорно искать человека, который бы разделял его взгляды на необходимость снаряжения такой экспедиции. Вскоре такое лицо нашлось. Это был советник Северного округа корабельных лесов П. Клоков, ученый лесничий, которого самого давно увлекала мысль возобновить старинный морской путь на Восток. Новая Земля представляла собой как бы промежуточную станцию на этой дороге.
В начале 1832 года образовалась торгово-промышленная компания архангельского купца Брандта и Клокова. Она-то и взяла на себя расходы по снаряжению и укомплектованию экспедиции. За это компания получала у царского правительства привилегию свободного промысла морского зверя в Северном Ледовитом океане в течение четверти века.
В экспедицию, которую снаряжала компания, входило два отряда. Один из них под командованием лейтенанта Кротова должен был на шхуне «Енисей» отправиться из Архангельска к проливу Маточкин Шар, пройти проливом в Карское море, а затем следовать к устью Енисея.
Другой отряд — Пахтусова — должен был произвести опись восточного берега Новой Земли. Полностью осуществить этот замысел не удалось — судно Кротова разбилось у западного входа в Маточкин Шар, и вся его команда погибла.
Назначенный начальником экспедиции, Пахтусов чувствовал себя бесконечно счастливым. Денег на постройку судна было отпущено в обрез, и Пахтусов сам работал над чертежами одномачтового карбаса.
Длина карбаса была 12,7, ширина 4,3, осадка 1,8 метра. В корме и на носу под палубой имелись крошечные каюты. Среднюю часть судна палуба не закрывала, ее заменяли брезенты, перекрывавшие друг друга. В наши дни на подобном кораблике не каждый даже опытный моряк решится выйти хотя бы просто порыбачить. А Пахтусова ожидал Ледовитый океан.
Вечером 1 августа 1832 года карбас, названный «Новой Землей», имея на борту, кроме начальника, девять человек команды, покинул Архангельск.
Море встретило смельчаков шквальными ветрами и сильным волнением, сменившимся густым туманом. 9 августа, когда рассеялся туман, вдали показался остров Колгуев.
В штурманской рубке, раскрыв свой дневник, Пахтусов перечел краткий и выразительный эпиграф, размашисто выведенный им на первой странице: «Я расскажу как было, а вы судите как угодно». Под свежим впечатлением пережитого шторма он записал:
«Казалось, что каждый находящий на нас вал старается покрыть судно наше седым своим гребнем, но бот наш гордо рассекал валы и несся на хребтах их, не страшась ярости бури».
Вечером впереди показалась полоска Новой Земли. Пока судно лавировало среди льдин, выискивая разводья и узкие полоски чистой воды, Пахтусов на шлюпке пошел осматривать пролив между островом и мысом.
«Не более как в час, — отметил он в дневнике, — убили мы тут 12 гагар и сварили их в братском нашем котле. Эта пища показалась нам очень вкусною».
«Братский котел» символизирует дружеские отношения между членами команды. Эти отношения, созданные Пахтусовым, никогда не нарушались, что не в малой мере способствовало успеху экспедиции.
Погода ухудшилась. Короткое и холодное северное лето было на исходе. Чем дальше на восток уходил карбас, тем непреодолимее становились препятствия. Но Пахтусов не хотел возвращаться назад, второй такой случай мог представиться не скоро.
«Частые неудачи в описи от туманов, дождей и большей частью от льдов, — записал он в дневнике, — делали положение наше для меня невыносимым. Мысль, что, несмотря на раннее еще время, придется нам зимовать, не увидев восточного берега, меня крайне беспокоила. Только примеры предшествовавших экспедиций в полярные страны несколько ободряли меня. Я знал, что и в позднюю осень Карские Ворота бывают иногда чисты ото льда».