English walrus hunters first sighted the south point of Nordaustlandet in 1617. This discovery was shown on the Muscovy Company's map (1625; but based on discoveries made in and prior to 1622), with the island labeled as Sir Thomas Smyth's Iland. It also shows the North Cape (Point Purchas). It is first named Oostlandt ("East Land") on a Dutch map of 1662, and the following year another Dutch map marked its coastline more distinctly, showing its west and north coasts, separating the latter from the Seven Islands (Sjuøyane). A Dutch map of 1710 was the first to show the island accurately, naming it Het Noord Ooster Land ("The North-east Land").
The rock types in Nordaustlandet stem from many different geological eras. The northern part consists of old crystalline basement, with rocks such as marble, quartzite, mica schist, gneiss and granite. East of Lady Franklinfjorden, on the peninsula Botniahalvøya and east of Duvefjorden there are volcanic rocks. In the east and south of Rijpfjorden the bedrock is made up of distinctive red-coloured granite. The Rijpfjord granite is medium grained, and contains two micas (muscovite and biotite) in addition to quartz, plagioclase and pink K-feldspar. It was emplaced in late Silurian times.
Layered gabbro and dolerite of Silurian age occur at Kapp Laura in easternmost Nordaustlandet, on the island of Storøya, and in the eastern part of the island of Kvitøya. On Andréeneset, in the southern part of Kvitøya, gneisses and granites are the most common rock types. Four generations of rocks: gneiss, amphibolite, and grey and pink granite are present on Isispynten, a headland east of Austfonna. South of Wahlenbergfjorden there is a large area with sedimentary rocks – mostly limestone and dolomite – from the Carboniferous and Permian. The youngest rocks in Nordaustlandet are Jurassic–Cretaceous dolerite dikes, which intrude the basement rocks on the island of Lågøya and in the outlet of Brennevinsfjorden.
Unconsolidated deposits in Nordaustlandet consist of scree slopes, block fields and raised shore deposits. There are only small amounts of river deposits. The largest strandflats on Nordaustlandet can be found in the north-west, around Murchisonfjorden and on the island of Lågøya. Another large strandflat is Svartknausflya in the south, just west of the glacier of Bråsvellbreen. Here, there are raised shore deposits up to 120 m.a.s.l., where ancient whale bones have been found 70 m (230 ft) above today’s sea level. Svartknausflya is also the largest moraine area in Nordaustlandet; it measures about 70 km2 (27 sq mi).
Glacial activity has shaped the landscape in Nordaustlandet through several ice ages. Gentle plateaus and rounded mountains are the most common sight. The tallest and steepest mountains, up to 600 m.a.s.l., can be found in the north. The eastern part of Nordaustlandet is covered in glaciers, and there are few areas without ice. Between Vibebukta and Kapp Laura, the steep front of the Austfonna ice cap dominates. The glacier has retracted a bit during recent decades, revealing new areas of dry land on the few headlands that can be found around here (such as Isispynten). Austfonna, including Vegafonna, stretch across an area of 8,450 km2 (3,263 sq mi). Austfonna covers approximately 58% of Nordaustlandet. Vestfonna is 2,445 km2 (944 sq mi). The largest areas with no ice are between Austfonna and Vestfonna and on the peninsulas in the north and north-west of Nordaustlandet.
The glacier Bråsvellbreen is a branch of Vestfonna. In 1937-1938 it had one of the largest surges ever recorded in Svalbard. The 30 km-wide (19 mi) glacier front 20 km (12 mi) forwards and into the ocean.