Az expedíció 1872. június 13-án indult útnak Bréma kikötőjéből. A Tegetthoff Novaja Zemljától északra jégtorlódásba került, és a jégtáblák közé fagyott. A jégbe zárt hajó észak felé sodródott egészen a 80. szélességi fok közelébe. 1873. februárjában a hajót hordozó jégmező nyugatias irányban kezdett elmozdulni. Közben az expedíció tagjai meteorológiai méréseket végeztek és vizsgálták a jégviszonyokat. 1873. augusztusának végén ÉNy felől egy szárazföld szegélyét pillantották meg. 1874. márciusában egy kisebb csoport partra szállt, és Payer vezetésével felderítő útra indultak észak felé. Egy hónapig ember által még soha nem látott csodálatos jégvilági tájakon jártak, és térképeztek fel kb. a 82. szélességi fokig. A nyugatra lévő nagy szigetet Wilczek-földnek, a keletit Zichy-földnek nevezték el, egy kiugró sziklás félsziget pedig a Budapest-fok nevet kapta. Az egész szigetvilágot Ferenc József császárról keresztelték el. Az expedíció tagjai tisztában voltak azzal, hogy a szigeten a pusztulás vár rájuk. A féloldalra dőlt hajóról lehordták a legszükségesebb felszereléseket, élelmiszereket és szánokra rakva megindultak dél felé. Szántalpakra szerelve magukkal vonszolták három csónakjukat is, hogy szükség esetén vízre szállhassanak. Közel három hónapos kimerítő vándorlás után augusztus közepén elérkeztek a jégmező peremére, melytől délre már a nyílt tengervíz húzódott, a távolban pedig feltűntek a Novaja Zemlja északi hegyei. Az expedíció történetét és felfedezéseit Julius Payer dolgozta fel könyvben.