Гьодел е познат преди всичко с неговите теореми зе непълнота, публикувани през 1931, когато е бил на 25 години, една година след защитата на докторската си дисертация във Виенския университет. По-известната теорема за непълнота гласи, че за всяка вътрешно непротиворечива, рекурсивна аксиоматична система, достатъчна за да опише аритметиката на естествените числа (Аритметика на Пеано), съществуват верни твърдения за естествените числа, които не могат да бъдат доказани в рамките на тази аксиоматична система.
Той доказва, че хипотезата за континуума не може да бъде отхвърлена в рамките на теорията на множествата, ако нейните аксиоми са непротиворечиви. Той прави и съществени приноси в теорията на доказателствата, изяснявайки връзките между класическата, съждителната и модална логика.