發表於1931年。它包括兩個定理：
第一不完備性定理 設S是包含算術系統在內的任意形式系統，則存在命題F使得F和它的否命題¬F都在S中不可證。這裏的F也稱為系統S內的不可判定句。
第二不完備性定理 在上述形式系統S中不能證明它本身的協調性。
K.哥德爾最初想證明希爾伯特計劃中企圖證明的形式數論系統和形式實數系統的協調性。他的想法是：①證明形式數論系統的協調性；②證明形式實數系統對於形式數論系統的相對協調性。他認為①是容易證明的，因此首先考慮②的證明。在考慮②的過程中發現瞭第一不完備性定理，證明的方法主要是對角線方法。
希爾伯特想要在各個古典數學形式系統裡，用有窮方法證明本系統的協調性。第二個完備性定理證明瞭即使在形式數論系統中希爾伯特計劃也無法實現，需要另謀其他出路。希爾伯特猜測隻要適當選擇比系統內所含有工具更強的工具就可以證明形式數論系統的協調性。果然在1936年G.根岑實現瞭他的猜測。
哥德爾給出的上述S內不可判定命題的直觀意思是“F在S內不可證”，即它的直觀是邏輯性質的。後來J.帕裡斯給出瞭一個S內不可判定的命題，它是有明顯的數學性質的真命題。在裴裡斯之後一些數學傢們又做出瞭不少有意義的工作，其中H.弗裡德曼的工作很受人註意。
第一不完備性定理的證明方法對遞歸論的早期發展有很大影響。