L'expédition quitte Saint-Pétersbourg en mai 1876, et se rend à Semipalatinsk (aujourd'hui Semeï au Kazakhstan), puis à Kulja (Yining), dans la vallée de l'Ili alors occupée par les Russes. Dix hommes, 24 chameaux, 4 chevaux et deux chiens se mettent en route à travers les Tian Shan, avec la double autorisation de Yaqub Bey (en), l'homme fort local, et des Chinois, qui s'apprêtent à regagner militairement la Dzoungarie et la Kachgarie. Les musulmans les interceptent et leur imposent d'aller directement à Korla.
De là, ils longent le fleuve Tarim « le pire endroit que je connaisse pour la chasse ». Même l'intérêt scientifique est limité. Fin décembre, à 600 km de Korla, le Tarim se perd dans les étendues de roseaux du Lop Nor, inconnu des Occidentaux depuis Marco Polo. Prjevalski constate que le Lop Nor n'est pas au même endroit que sur les cartes anciennes (où il figure plus au nord-est). Noël voit l'expédition à Charklik (Ruoqiang), au pied de l'Altyn-Tagh (en), dont elle explore les contreforts, dans le vent et la neige. La faune est peu abondante, mais un chameau sauvage s'approche de la caravane, sans qu'on puisse le prendre. Prjevalski rapportera néanmoins trois peaux, fournies par des locaux. Au printemps 1877, 27 espèces d'oiseaux migrateurs sont observées sur les bords du Lop Nor. Le rêve de Tibet s'estompe : il ne reste que cinq chameaux, et aucun guide ne peut être trouvé. Prjevalski décide de retourner à Kulja. À Korla, il rencontre Yaqub Bey (« Yaqub Bey is the same shit as all feckless asiatics »). Les chameaux meurent un à un. Partout, les Mongols sont pourchassés et exterminés par les musulmans.
À Kuldja, Prjevalski apprend sa promotion comme colonel. Son prochain départ pour Lhassa prendra une autre route, autour de la Dzoungarie, vers Hami et le Tsaidam. Mais dès novembre, à Guchen (Qitai), au pied des monts Bogda Shan (en) (à l'est d'Urumqi), Prjevalski est malade, irascible, ne parle plus à ses Cosaques. Il décide de se rendre à l'hopital de Zaïssansk, la première ville russe, au pied de l'Altaï, à 700 kilomètres de distance. En janvier et février 1878, il se soigne, et alors que l'expédition se prépare à son troisième départ, un messager vient leur demander de s'arrêter en raison de la situation diplomatique avec la Chine. Il s'exécute, décidé à repartir dès que possible, et rapporte néanmoins à Saint-Pétersbourg un butin botanique et zoologique considérable.
Pour son exploration au Lop Nor, Prjevalski reçoit les médailles de toutes les sociétés de géographie européennes, et tente d'obtenir par tous les moyens les autorisations nécessaires à un nouveau départ. Il écrit notamment : « L'intention scientifique masquera les objectifs politiques de l'expédition et détournera toute suspicion de la part de ceux qui nous sont hostiles. »
Prjevalski arrive à Saint-Pétersbourg en janvier 1886. Il se sent habilité à exprimer des positions impérialistes. Dans un texte intutulé « Un aperçu de la situation présente en Asie Centrale », il explique comment « la loi internationale ne s'applique pas aux sauvages » et il prône l'annexion par la Russie des poulations mongoles et musulmanes.
Son obsession de parvenir à Lhassa ne l'a pas abandonné. Après deux années partagées entre son domaine et les cercles de Saint-Pétersbourg, il prend le nouveau chemin de fer transcaspien pour Samarcande, puis se rend à Tachkent et Frounze (Bichkek). En préparation de l'expédition, il part chasser dans une région touchée par une épidémie de typhoïde chez les Kirghizes, boit imprudemment l'eau d'une rivière, et tombe malade. Après trois jours de route vers Karakol, il est hospitalisé, et meurt en quelques jours, après avoir demandé d'être enterré à proximité.
L'expédition part quand même, sous la direction de Pevtsov, explorateur de la Mongolie et du Turkestan dépêché en dernière minute, avec pour mission de rester dans les confins nord du Tibet. Ils iront à Yarkand et aux oasis du sud du Taklamakan, en explorant toutes las vallées conduisant au plateau.
En 1893, Alexandre III renomme la ville de Karakol en Prjelvalsk, décision inversée par Lénine en 1921, puis de nouveau par Staline en 1939 (pour le centenaire de la naissance de Prjevalski).
La mémoire de Prjevalski est entretenue dans trois œuvres littéraires : Gontcharov, rencontré à Khabarovsk, raconte leur rencontre dans sa Frégate Pallas. Dans Le Duel, Tchekhov le peint sous les traits de von Koren. Nabokov s'inspire de lui dans Le Don.