Expeditionens fartyg, ångaren Tegetthoff, om 300 tons, utrustades i Elbe med tillgodoseende af alla moderna hjelpmedel, försågs med proviant o. dyl. för 2-1/2—3 års tid och utgick slutligen från Bremerhaven den 13 Juni 1872. Största delen af manskapet utgjordes af dalmatier från Adriatiska 43 hafvets kust. Såsom ismästare medföljde särskildt kapten E. Carlsen från Tromsö, hvilken gjort sig väl känd derigenom, att han kringseglat både Spetsbergen och Novaja Semlja samt hemfört relikerna från Barents’ vinterhydda i Ishamnen. Efter några ytterligare anordningar i Tromsö lemnade expeditionen denna stad den 14 Juli.
Den 19 Juli möttes den första isen vid 74° 15´ n. br., den 29 Juli kom man i sigte af Novaja Semlja, och den 12 Augusti sammanträffade Tegetthoff vid Pankratjefföarne med slupen Isbjörn, som med grefve Wiltschek ombord var utgången för att nedlägga en proviantdepot för expeditionens räkning på Novaja Semljas vestkust. Den 21 Augusti togo de båda fartygen afsked af hvarandra, Isbjörn vände åter till Norge, och Tegetthoff ångade norrut på sin storartade upptäcktsfärd. Förr än efter två års förlopp borde man icke hoppas att erhålla några underrättelser från den väl anlagda expeditionen, ty sedan man passerat Novaja Semljas nordspets och framträngt österut till Tajmyrlandet, hade man för afsigt att tillbringa första vintern i närheten af kap Tscheljuskin, Sibiriens nordligaste udde, och den andra någonstädes på de Nysibiriska öarne eller möjligen på Wrangels land.
Men expeditionen fick en helt annan utgång, än man med skäl hade väntat sig. Redan några timmar efter de båda fartygens skilsmässa hade en frisk nordostlig vind skjutit så mycket is samman kring Tegetthoff, att rundtomkring icke var en enda smula vatten att se. Detta inträffade vid 76° 22´ n. br. och 62° 3´ ostl. längd från 44 Greenwich, på ungefär sex mils afstånd från kusten. »Jag hade förtöjt fartyget», säger Weyprecht, »vid ett flak, fullt medveten derom, att det skulle blifva instängdt. Å ena sidan kunde jag icke besluta mig för att låta de 15 mil åter gå förlorade, som vi lyckligt vunnit under de detta år ogynsamma förhållandena, å andra sidan utgjordes all den kring oss liggande isen af så sönderbråkad drifis, att jag med visshet räknade på, att första ostliga vind skulle föra alltsammans åtskils. Men i stället för ostliga vindar, som jag hade väntat skola efterträda de föregående veckornas ihållande våldsamma sydveststormar, inträdde nu stiltje omväxlande med vestliga vindar. De senare medförde ganska mycket snö, som i förening med temperaturens snabba sjunkande sammanband drifisen. Ända till den 9 September gafs der ingen förändring, isen låg tätt sluten, åt intet håll kunde man se ett spår af vatten. Fartyget dref för de lätta vindarne än åt öster, än åt vester. Temperaturen föll under nätterna ända till -15° C.» Den 9 September utbröt ändtligen en häftig storm från nordost, som sönderbröt isen i större fält, men fartyget låg fortfarande infruset midt uti ett sådant, och alla ansträngningar att arbeta det loss förblefvo fruktlösa.
Tegetthoffs väg var från denna stund och allt framgent bunden vid isfältets rörelser, och detta fördes af och an allt efter vindarnes godtyckliga nycker. Den 1 Oktober befann sig fartyget vid 76° 50´ n. br. och 65° 22´ ostl. längd från Greenwich, och den 5 i samma månad förlorade de Novaja Semljas kust ur synhåll. De voro icke 45 längre upptäcktsresande i den meningen, att de kunde fritt bestämma sin väg, utan passagerare på ett isfält, som tog sin väg deras vilja förutan.
Den 13 Oktober gick det väldiga isfältet i stycken under ett fruktansvärdt tryck från alla sidor, och från denna dag togo de förfärliga ispressningarna sin början, hvilka sedan upprepades med korta mellanrum nästan hela vintern igenom. Der bildade sig gång efter annan stora remnor i isen, isfälten sköto samman, under och öfver hvarandra, fartyget höjdes och sänktes allt efter ispressningarnes våldsamhet, det befann sig i en ytterst bekymmersam belägenhet, och under sådana förhållanden måste naturligtvis allt hållas i beredskap, för att man vid första påminnelse skulle kunna öfverge fartyget. Ett hus af stenkol, som blifvit uppfördt på isen för att tjena som tillflyktsort i händelse af fartygets förlust, förstördes under en rörelse i isen julveckan, och senare, under Januari månad 1873, nådde ispressningarna höjdpunkten af våldsamhet; den 22 Januari pressade sig en ismur upp på några få stegs afstånd från fartyget till 30 fots höjd, och samtidigt förstördes ett tält för magnetiska iakttagelser och ett upplag af stenkol och ved. Under de fem månader, som ispressningarna varade, kommo österrikarne föga till ro, endast sällan kunde de våga kläda fullständigt af sig. Den 16 Februari steg solen åter öfver horisonten efter 109 dygns frånvaro, och kort derefter, den 25. Februari, upphörde ispressningarna lika hastigt och oväntadt, som de börjat hösten förut. Fartyget dref oupphörligt mot nordost, och de resande förestälde 46 sig till och med, att de skulle komma att föras mot Sibiriens kust; men när de den 4 Februari skurit 73:e längdgraden, kantrade vinden om, och från denna dag fördes de, fortfarande lika hjelplösa som förut, mot nordvest. Mot slutet af Februari månad nådde temperaturen sitt minimum för vintern, -46°,2 Celsius.
När sommaren 1873 inträdt, begyntes arbetena för att befria fartyget. Månaderna Maj, Juni, Juli och Augusti användes för att såga igenom det väldiga isfältet, men derigenom att andra isfält under ispressningarna banat sig väg in under det, hade det nått en tjocklek af 40 fot, och alla ansträngningar visade sig fullkomligt gagnlösa. Först i Juni sågo österrikarna från utkikstunnan enstaka öppningar i isen på stort afstånd, framdeles visade sig också här och der smärre vakar, men aldrig någonstädes egentligt öppet vatten. Isfältet, som under våren syntes hafva hvarken början eller slut, blef under hösten allt mindre och mindre. Utsigten att få tillbringa en andra vinter under liknande faror och overksamhet som den första syntes mycket stor, och österrikarne voro redan förberedda derpå, men då förändrade sig helt oväntadt ställningen till deras fördel.
»Sedan lång tid tillbaka», säger Payer, »hade vi blifvit drifna omkring i en del af norra Ishafvet, som förut icke varit af någon besökt, men oaktadt en omsorgsfull utkik hade vi hittills icke kunnat finna något land. Det var för den skull en händelse af icke ringa betydelse, då vi den 13 Augusti öfverraskades af det plötsliga framträdandet af ett bergigt land, omkring 14 eng. mil norr ut, 47 hvilket dimman ända till denna tid hade dolt för våra blickar. Vid detta tillfälle glömde vi all vår förra oro; oförtöfvadt skyndade vi mot land, ehuru fullt öfvertygade derom, att vi icke skulle vara i stånd att komma längre än till randen af vårt isflak. Månader igenom voro vi nu dömda att lida en Tantali qval. Tätt inpå oss hade vi ett nytt polarland, rikt på löften om upptäckter, men nu, beroende som vi voro af vindens växlande nycker och omgifna af öppna vakar, voro vi oförmögna att komma det en hårsmån närmare. Ändtligen, mot slutet af Oktober, närmade vi oss på tre mils afstånd en af öarne, som bildar förposten till hufvudlandet. Vi togo vägen öfver de upptornade och hopskrufvade isblocken och satte så för första gången vår fot på det obekanta landet vid 74° 54´ n. br. Isen, som betäckte hafvet närmast kusten, var endast en fot tjock; det var alltså tydligt, att här hade under den nu gångna sommaren funnits periodiskt öppet vatten. En mera öde ö än denna, som vi kommit till, kan svårligen tänkas, ty snö och is betäckte hennes frusna och steniga sluttningar. Men för oss var hon af sådan vigt, att vi med henne förenade namnet på den person, som var den egentlige upphofsmannen till vår expedition, grefve Wiltschek.»
I September och Oktober dref fartyget längs efter kusten af det nyupptäckta landet, men i början af November frös isflaket, hvarpå det var uppressadt, tillsammans med den fasta landisen vid 79° 51´ n. br. och 58° 56´ ostl. längd från Greenwich. Der blef det orubbligt liggande på 48 3 sjömils afstånd från närmaste strand, ända tills österrikarne måste öfverge det den följande sommaren. Fartyget hade redan blifvit ombonadt för att möta öfvervintringen, och under första hälften af Oktober hade ispressningarna åter gjort sig påminta, men sedan Tegetthoff låg orörligt fast vid landisen, förekommo de icke mera under vinterns lopp. Den 22 Oktober gick solen ner för att icke åter visa sig öfver horisonten förr än efter 125 dygns förlopp.
I November uppfördes två snöhus på isen för att hysa de fixa magnetiska och astronomiska instrumenten, och när dessa blifvit uppstälda der, begyntes med nyårets inträde 1874 de regelmässiga magnetiska variationsiakttagelserna. Den första vintern hade varit odräglig till ytterlighet i följd af de ständiga ispressningarna; den andra vintern bildade i detta afseende en fullkomlig motsats mot den förra, men i stället förekommo nu ihållande häftiga snöstormar, som upphörde först i Maj månad. När man insett nödvändigheten och följaktligen öfverenskommit att öfverge fartyget, rustade sig Payer att före hemfärden ge sig åstad mot norden på slädfärder för att kartlägga det nya landet, hvaremot Weyprecht stannade qvar om bord som förut, sysselsatt med anordningarna för hemresan och afslutandet af de vetenskapliga iakttagelserna.
Payer företog under våren 1874 tre särskilda slädfärder, hvilka begyntes den 10 Mars och afslutades den 3 Maj. Den första och sista af dessa färder varade blott några få dagar. Under den första slädfärden, som tog sin början den 10 Mars, var kölden ganska stark och steg vid 49 ett tillfälle till -50° C. (samtidigt observerades om bord -43°,3 C.). »Vi voro tvungna», säger Payer, rätt iakttaga den största försigtighet; vår nattsömn i tältet blef störd, och öfvergången af Sonklar-glacieren under en obetydlig bris var ytterligt pinsam. Våra kläder voro styfva som ett pansar, och till och med vår rom, ehuru ganska stark, tycktes hafva förlorat både sin kraft och sin fluiditet. Vi sofvo i fyra rockar, men om dagen funno vi kläder gjorda af fågelskinn vara de lämpligaste att motstå klimatets stränghet. Oaktadt all försigtighet ledo vi emellertid mycket af frostskador, mot hvilka en blandning af jod och kollodium visade sig verksammast.» Den andra slädfärden begyntes den 24 Mars, och i denna deltogo, förutom Payer, sex andra personer jämte tre hundar. Släden var lastad med proviant och andra förnödenheter till en vigt af 16 centner. Tvärt emot de förväntningar, man hade skäl att hysa, sjönk temperaturen under denna resa icke under -32°,5 C., men snödrifvor och fuktighet, vakar i isen och vattnets öfversvämning, der vägen gick fram, voro till stort bekymmer. Den 26 Mars passerades 80:e breddgraden och den 3 April den 81:a. Den 12 April var den sista dag, som Payer framgick mot norden; temperaturen var då -12°,5 C. Han vände om vid 82° 5´ n. br. och återkom, efter jämt en månads frånvaro, till fartyget den 24 April. Frukten af denna slädfärd var en kartläggning af det nya landet, som sedermera erhöll namnet Frans Josefs land, norr ut ända till 83:e breddgraden. När den tredje slädfärden var bragt till slut, uppmätte Weyprecht för kartläggninrande 50 nordostpassagens utförbarhet? — Jag skall påpeka, hvad Payer och Weyprecht omedelbart efter hemkomsten 1874 uttalat om möjligheten af en sådan passage. Weyprecht skrifver bland annat i bref till Petermann sålunda: — »För det tredje har frågan om möjligheten att framtränga mot öster längs efter Sibiriens kust alldeles i ingen mån modifierats genom resultaten af vår expedition. Den plan för expeditionen, som jag i December 1871 framlade för vetenskapsakademien i Wien, anser jag fortfarande lika utförbar som då, och jag skulle eventuelt än en gång vara beredd att utföra densamma.» Payers uttalande i frågan går deremot i alldeles motsatt riktning. Han säger, likaledes i bref till Petermann: »Der gifves intet öppet och intet fullkomligt slutet polarhaf, men der finnes en viss årligen växlande chance för skeppsfart. Denna chance tänker jag mig dock aldrig någonsin så stor, att man skall kunna uppnå polen eller utföra nordostpassagen.»