In 1921, Hilbert had this idea, that mathematicians could create an algorithm that would automatically prove every true statement and disprove every false statement. Wouldn't that be neat? It's important that this idea predates computers. When Hilbert was thinking about an algorithm, it wasn't an algorithm as we would think about it in computer science today, because the modern idea of a computer hadn't been formalized.
In 1931, Godel proved that it was impossible for an algorithm to automatically prove or disprove true mathematical statements. Take that, Hilbert. The modern idea of a computer still hadn't been formalized. So a lot of stuff that nowadays we think of as simple, Godel did in a really weird and confusing way.
For example, as part of his proof Godel needed a way to algorithmically encode a bunch of numbers into a single number. Nowadays, that's pretty intuitive - any software program can be saved into a file, any file can be interpreted as a sequence of binary bits, which can be interpreted as a number. Back then, Godel used a really crazy encoding - encoding (a, b, c, d, ...) as 2^a * 3^b * 5^c etc.
So if you go back and try to understand Godel's proof, it is really just needlessly complicated. I loved the book Godel, Escher, Bach when I first read it, but once I understood the mathematics more deeply I started thinking that it really wasn't the best approach to actually understand the mathematics.
In 1936, Turing defined a Turing machine and also proved that the halting problem was undecidable. This is an equivalent statement to Godel's incompleteness theorem, and the proof is about 100 times more intuitive, especially for modern computer programmers who tend understand computers and computer programs pretty well, far better than they understand prime factorization.
So, personally I think if you are learning this stuff, you are better off starting by learning about the halting problem. Sometimes the historical sequence of discovery isn't the best way to learn math, just like we don't learn about the Greek method of exhaustion before we learn modern methods of calculus.