W roku 1931 opublikował pracę „Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme. I.”, w której sformułował twierdzenie o niezupełności. Praca ta została przyjęta jako praca habilitacyjna (zaakceptowana przez Hansa Hahna) i od marca 1933 roku Gödel objął w Uniwersytecie Wiedeńskim stanowisko Privatdozent.
W roku 1934 Gödel przybył do Princeton z cyklem wykładów „O zdaniach nierozstrzygalnych w sformalizowanych teoriach matematycznych”. Wykłady spotkały się z uznaniem, lecz z nieznanych powodów Gödel doznał załamania nerwowego i powrócił do Europy w depresji, wymagającej kilkumiesięcznego leczenia psychiatrycznego w sanatorium.
Niezależnie od problemów zdrowotnych Gödel funkcjonował jako uczony, uzyskując w roku 1935 rezultaty w badaniach nad pewnikiem wyboru. Po zamordowaniu profesora Uniwersytetu Wiedeńskiego Moritza Schlicka (który zainteresował Gödla logiką) przez chorego psychicznie studenta Johanna Nelböcka, uczony doznał kolejnego załamania nerwowego.