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

Холодной, суровой зимой, уйдя в пустыни Тибета, населенные воинственными тангутскими племенами, Пржевальский надолго исчез из поля зрения китайской администрации. Подвергшись нападению тангутов, экспедиция с боем пробилась через их окружение и невредимой вышла в Центральный Тибет.

Пока шли трудные экспедиционные будни, в Пекин доносились вести об исчезновении Пржевальского, о его гибели. Слухи распространялись очень быстро, и уже скоро русская столичная печать писала о смерти путешественника. В поисках следов Пржевальского усиленно переписывался русский поверенный в делах в Пекине А. И. Кояндер с китайскими министрами. Последние ссылались на то, что Северный Тибет населен непокоренными тангутами, не признающими власти китайских чиновников, на труднопроходимые горные перевалы, занесенные снегом, и говорили, что при таких условиях гарантировать жизнь путешественников китайское правительство не может.

Ссылка на несостоятельность китайского влияния в Тибете явно имела характер дипломатического хода. В то время в Лхасе жили постоянные китайские резиденты; на их помощь напрасно надеялся Пржевальский, когда полагал, что выдача ему китайского паспорта и визы для следования в Тибет обеспечит защиту и поддержку китайских представителей при далай-ламе.