Las autorités militaires lui demandent d'examiner la disposition des bataillons des frontières mandchoue et coréenne, d'étudier la population, la faune et la flore, ainsi que les routes terrestres, fluviales et maritimes. Son jeune ami Koecher lui fait faux bond, et Prjevalski trouve un autre compagnon de voyage, Nikolaï Iagounov. L'expédition se met en route le 7 juin 1867. Elle traverse le lac Baïkal en steamer, puis rejoint la rivière Chilka, le premier affluent majeur de l'Amour, et fait route vers Blagovechtchensk puis le village de Khabarovka (aujourd'hui Khabarovsk), au confluent de l'Oussouri. De là, l'Amour coule vers le nord-est, et l'Oussouri vers le sud. Sur 500 kilomètres, l'expédition remonte le cours de l'Oussouri, passant les 27 stations de colons cosaques jusqu'au village de Busse, qui gardent la frontière chinoise, puis atteint le grand lac Khanka. Tout le mois d'août 1867 est consacré à l'observation, la chasse et la pêche sur les abords du lac. En septembre, le poste de Possiet sur la côte Pacifique est atteint, à 160 kilomètres au sud. Prjevalski force la frontière coréenne, jusqu'à la forteresse de Keiko, considérant que c'est ainsi qu'il faut agir avec les Asiatiques. L'expédition remonte ensuite de mauvaises pistes côtières sur 500 kilomètres jusqu'à Vladivostok, peuplée alors de 500 habitants. Après une infructueuse chasse au tigre dans la vallée de Soutchan, l'expédition passe la baie d'Olga, puis remonte la vallée de la Tazoucha à travers les monts Sikhote Aline. Elle arrive dans la vallée de l'Oussouri et passe un printemps 1868 bucolique au lac Khanka, où elle recense 120 espèces d'oiseaux. Prjevalski est appelé à pacifier un soulèvement anti-russe des Chinois de la vallée de Soutchan, puis il est appelé à Nikolaïevsk, pour y occuper des fonctions militaires qu'il apprécie peu.
Son travail d'exploration lui vaut une médaille d'argent de la société de géographie (le compte rendu « Voyages dans la région de l'Oussouri » sera publié en 1870), et il peut enfin rentrer à Irkoutsk à l'automne 1869, puis à Saint-Pétersbourg pour la nouvelle année.
Le président de la Société de géographie, Piotr Semionov-Tian-Chanski, lui promet son soutien pour une expédition dans l'ouest de la Chine, mais la région est en proie à la rébellion des Dounganes, des Chinois de religion musulmane. Prjevalski obtient néanmoins la permission de monter une expédition vers le lac Kokonor, point de rencontre des Chinois, des Mongols et des Tangoutes (Tibétains nomades). L'expédition est financée par la Société de géographie, le ministère de la guerre, Prjevalski lui-même, et le jardin botanique. L'ambassade russe à Pékin se charge d'obtenir les passeports.
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.