Dès février 1879, le nouveau groupe parvient à Orenbourg, le nouveau terminus ferroviaire, puis à Zaïssan (en), à la frontière de la Dzoungarie. Les risques sont grands, mais Prjevalski a le sentiment d'être dans une course pour atteindre Lhassa, contre le comte hongrois Béla Széchenyi et les Anglais. Avant de partir, il entraine au tir ses compagnons car « C'est le meilleur passeport qu'on puisse obtenir pour la Chine ».
Le départ effectif est donné en avril, en direction des oasis de Barköl et de Hami, dans l'est de la Dzoungarie, par un itinéraire qui suit la frontière de la Mongolie, au pied de l'Altaï. Juste après le départ, des Kirghizes montrent à Prjevalski la peau d'un cheval sauvage, qu'ils appellent le kurtag et que les mongols appellent le takhi. Peu après, il en observera des spécimens vivants. C'est cette espèce qu'on appelle aujourd'hui cheval de Prjevalski. Hami est alors une ville-oasis d'une importance stratégique militaire majeure, reliant la Dzoungarie et la vallée de l'Ili à la Chine. Elle est peuplée de 4 500 soldats et de 5 000 civils, Dounganes, Ouïghours et immigrants chinois.
L'expédition fait route vers Dunhuang (alors appelée Sa-chou), le site des fameuses grottes bouddhistes de la route de la soie. Prjevalski y fait une rapide visite (mais les « dieux imaginaires » n'ont pas sa faveur), et campe une semaine à proximité de la ville. Face à l'interdiction du général chinois commandant la région, Prjevalski feint une partie de chasse pour s'éloigner vers le sud et passer au Tsaidam à travers les montagnes. Ses guides chinois tentent de le perdre, et il les renvoie, devant trouver seul son chemin à travers un massif aride qu'il nomme la chaîne de Humboldt, en l'honneur du géographe allemand. Les habitants du nord du Tsaidam sont des Mongols qui acceptent de guider l'expédition à travers les monts Ritter, jusqu'aux lacs Yikhe (grand) et Baga (petit) Tsaidamyn. Via le lac Kurlyk, vers l'est, l'expédition atteint la rivière Bayan, puis Dzun Zasak, au sud du Tsaidam, un lieu déjà visité sept ans auparavant.
On est au début de l'automne, et Prjevalski est résolu à gagner Lhassa « par la menace ou par la subversion ». Cette fois, les chameaux sont en bonne santé. Un messager chinois lui demande de nouveau de s'interrompre, mais il n'en a cure. Le risque est pourtant important car la Chine et la Russie sont presque en guerre sur la question de l'Ili. Passé le premier rideau de montagnes, Prjevalski a le plaisir de trouver de grands troupeaux de yaks et de d'ânes sauvages, et il en chasse beaucoup plus qu'il ne peut en consommer. Pour éviter sa route de 1872, l'expédition oblique à l'ouest et parvient à la rivière Shuga. De nouveau, la chasse est trop facile et en devient lassante. Sur la rive du premier affluent du Yangtse rencontré, des traces de chameaux témoignent du passage récent d'une caravane, devant eux. Malgré la météo, Prjevalski décide de tirer droit sur Lhassa. Il atteint la région de Kokoxili, où il trouve des roseaux pour nourrir les chameaux. Une nouvelle race d'ours est découverte.
Le guide s'égare et Prjevalski le renvoie vers le Tsaidam, s'il peut y parvenir. Il trouve un col conduisant au Mur Usu, le cours supérieur du Yangtse, environ 300 km en amont de sa visite précédente. On est là sur l'une des routes principales de pèlerinage qui conduit à Lhassa, via les monts Tangula. L'expédition remonte la rivière qui entre dans un défilé, et les traces sont perdues. La progression est très difficile, à travers des cols dépassant les 5 000 mètres d'altitude. Mais on atteint les premiers groupes humains depuis le Tsaidam. Ce sont des tribus Yograi, qui ne reconnaissent ni l'autorité de Xining, ni celle du dalaï-lama. Faute d'interprète, la communication est impossible avec eux, et ils se montrent hostiles. Plusieurs escarmouches se produisent, opposant douze européens à « des hordes de sauvages », dont plusieurs sont tués. Un pèlerin mongol indique que Lhassa s'inquiète de leur approche. La frontière est gardée entre les Tangula et le fort de Nagchu. La population est menacée de mort si elle leur vend des vivres. À vingt kilomètres au nord de Nagchu, des soldats tibétains leur demandent poliment de s'arrêter. Lhassa n'est qu'à 250 km, mais Prjevalski doit obtempérer. Après trois semaines, des nouvelles arrivent de Lhassa, et le gouverneur de Nagchu lui intime l'ordre de quitter le Tibet. En arrivant au Tsaidam, il s'aperçoit qu'il avait été donné pour perdu ou mort.
En mars 1880, Prjevalski revient au Kokonor, puis à Xining, où le gouverneur militaire tente de le dissuader de partir vers les sources du Fleuve Jaune. L'expédition atteint Balekun Gomi, le dernier poste habité sur le cours supérieur du Fleuve Jaune, puis l'affluent Churmyn, mais il est impossible de remonter plus haut, et il faut rebrousser chemin. L'été 1880 est consacré à herboriser dans les montagnes du Gansu, avant un retour vers l'Ala Shan, puis Ourga atteint en octobre.
Le retour à Saint-Pétersbourg est triomphal, et culmine par une audience du Tsar Alexandre II. Prjevalski fait l'acquisition d'un domaine près de Smolensk, qu'il transforme en un paradis de chasseur. Dans la distillerie voisine, il repère le jeune employé Piotr Kozlov, qui deviendra son nouvel assistant puis un explorateur de renom. Il envisage déjà une nouvelle expédition, dont le premier objectif serait les sources du Fleuve Jaune. Puis autant de Tibet que possible, avant un retour via Kachgar et le lac Issyk-Koul (aujourd'hui au Kirghizistan). Certaines voix lui reprochent de ne pas être systématique dans ses explorations, et de ne pas s'intéresser à la géologie, à la linguistique, à l'archéologie, à l'ethnologie. Prjevalski accepte de centrer cette nouvelle expédition sur des compléments de recherches manquant dans les premières, mais il refuse de s'entourer de spécialistes civils.