Хотя Евклид не был самым изобретательным греческим геометром, а аксиоматический метод был известен и до него, его изложение геометрии вызывало всеобщее восхищение. Однако вскоре математики начали сознавать, что, несмотря на свою красоту и совершенство, работа Евклида содержала некоторые пробелы. Например, принятых аксиом было недостаточно для вывода всех теорем. Иногда попадались другие, несформулированные предположения, особенно связанные с наглядным представлением о невозможности пересечения определённых прямых линий. Кроме того, одна из евклидовых аксиом — постулат о параллельных прямых — казалась уж не такой очевидной и не могла быть принята на веру без доказательства. Один из многочисленных вариантов этой аксиомы, по существу, эквивалентен утверждению, что через любую точку вне данной прямой можно провести ровно одну прямую, не пересекающую данную прямую. Как правило, однако, этот и другие пробелы в евклидовой геометрии были не особенно серьёзными — их можно было легко устранить введением дополнительных аксиом, призванных восполнить явно не сформулированные предположения, либо доказательством сомнительной аксиомы в качестве теоремы или заменой её на более очевидную аксиому, либо, наконец, приведением отрицания этой аксиомы к противоречию. Последний, наиболее хитроумный способ решения проблемы постулата о параллельных прямых впервые ввёл в математику понятие совместности, или непротиворечивости.
По-видимому, Гаусс был первым математиком, который примерно в 1800 году пришёл к мысли, что отрицание евклидова постулата о параллельных прямых не приводит к противоречию и, тем самым, возможны геометрии, отличные от евклидовой. Так как эта идея уж слишком сильно попахивала метафизической спекуляцией, он никогда не публиковал этих исследований и лишь по секрету сообщил о них своим ближайшим друзьям.
В 1830 году два самобытных математика почти одновременно и независимо друг от друга вывели всевозможные следствия из евклидовых аксиом с измененной аксиомой о параллельных прямых. Их новая аксиома утверждала, по существу, что через данную точку вне данной прямой можно провести бесконечное число прямых, не пересекающих данную прямую. Так как полученные утверждения противоречили обычным представлениям, оба они — русский Лобачевский и венгр Я. Бояи — надеялись, что применение аксиоматического метода приведёт в конце концов к противоречивым теоремам. Однако ни одного противоречия в новой геометрии не было найдено, хотя теоремы, полученные из новой системы аксиом, и находились в резком противоречии с повседневной практикой (например, сумма углов треугольника была, в отличие от евклидовой геометрии, меньше двух прямых углов). Тем самым они обнаружили, что можно построить непротиворечивую геометрию, исходя из аксиом, не кажущихся очевидными (в отличие от евклидовых) и даже производящих впечатление неверных.
Однако удивительно, что открытие неевклидовых геометрий не вызвало «крика беотийцев», опасаясь которых, Гаусс (из письма к Бесселю от 27 января 1829 года) отказался от публикации своих исследований на эту тему. Больше того, это открытие даже не очень заинтересовало математиков. Для большинства из них оно было уж слишком абстрактным.
Только в 1870 году идея неевклидовых геометрий получила общее признание. Это произошло после того, как 21-летний Феликс Клейн обнаружил в одной работе Кэли «модель», позволяющую отождествить исходные объекты и соотношения неевклидовой геометрии с некоторыми объектами и соотношениями евклидовой геометрии. Этим он доказал, что неевклидова геометрия непротиворечива в той же мере, что и евклидова, — противоречие в одной из них необходимо влечёт противоречие в другой.