Gauss also claimed to have discovered the possibility of non-Euclidean geometries but never published it. This discovery was a major paradigm shift in mathematics, as it freed mathematicians from the mistaken belief that Euclid's axioms were the only way to make geometry consistent and non-contradictory. Research on these geometries led to, among other things, Einstein's theory of general relativity, which describes the universe as non-Euclidean. His friend Farkas Wolfgang Bolyai with whom Gauss had sworn "brotherhood and the banner of truth" as a student had tried in vain for many years to prove the parallel postulate from Euclid's other axioms of geometry. Bolyai's son, JŠnos Bolyai, discovered non-Euclidean geometry in 1829; his work was published in 1832. After seeing it, Gauss wrote to Farkas Bolyai: "To praise it would amount to praising myself. For the entire content of the work... coincides almost exactly with my own meditations which have occupied my mind for the past thirty or thirty-five years."

This unproved statement put a strain on his relationship with JŠnos Bolyai (who thought that Gauss was "stealing" his idea), but it is now generally taken at face value. Letters by Gauss years before 1829 reveal him obscurely discussing the problem of parallel lines. Waldo Dunnington, a biographer of Gauss, argues in Gauss, Titan of Science that Gauss was in fact in full possession of non-Euclidian geometry long before it was published by JŠnos Bolyai, but that he refused to publish any of it because of his fear of controversy.

The survey of Hanover fuelled Gauss's interest in differential geometry, a field of mathematics dealing with curves and surfaces. Among other things he came up with the notion of Gaussian curvature. This led in 1828 to an important theorem, the Theorema Egregium (remarkable theorem in Latin), establishing an important property of the notion of curvature. Informally, the theorem says that the curvature of a surface can be determined entirely by measuring angles and distances on the surface. That is, curvature does not depend on how the surface might be embedded in 3-dimensional space or 2-dimensional space.

In 1854, Gauss notably selected the topic for Bernhard Riemann's now famous Habilitationvortrag, ‹ber die Hypothesen, welche der Geometrie zu Grunde liegen. On the way home from Riemann's lecture, Weber reported that Gauss was full of praise and excitement.