When I first heard of the existence of Gödel's theorem, I was amazed not just at the theorem but at the fact that the question could be made precise enough to answer: how on earth, even in principle, could one show that it was impossible to prove something in a given system? That doesn't bother me now, and that is not my question.
It seems to me that Gödel's theorem is a combination of at least three amazing achievements, namely these.
Formalizing the notions of proof, model, etc. so that the question could be considered rigorously.
Daring to think that there might be true but unprovable statements in Peano arithmetic.
Thinking of the idea of Gödel numbering and getting the proof to work.
One might think that 3 constitutes two separate achievements, but I think that actually getting the proof to work, though pretty good going, is somehow a technicality once you have had the idea that in principle a proof along those lines might be possible. (I'm not saying I could have done it, but Gödel would have been deeply immersed in these ideas.)
My guess is that pretty well all the credit for 2 and 3 goes to Gödel (except that the idea of diagonal proofs was not invented by him). My question is how much he contributed to 1 as well. Had it occurred to anyone else that it might be possible to think about such questions rigorously, or did an entirely new way of thinking appear pretty well out of nowhere? Popular accounts suggest the latter, but common sense would suggest the former, at least to some extent.