Although the Leader had been mentioned in earlier issues, we first actually meet him in Tales to Astonish #63. The story follows the standard Marvel radioactive origin, with a janitor accidentally exposed to Gamma rays suddenly becoming a genius. Interestingly, he also turns green, which is what attracts his attention to the Hulk.
This origin and the huge crainium appear to be swiped from Detective #217's "The Mental Giant of Gotham City", which had been reprinted in Batman Annual #3 a few years earlier. Of course, that story borrowed liberally from the famed science fiction short story Flowers for Algernon, so it's a swipe of a swipe.
The Leader heads up a giant spy ring (although the only member we ever see is The Chameleon. He's as smart as the Hulk is strong, so their battles will be the classic brains versus brawn matchup.
The stories in this era begin to fall into a common pattern. Bruce Banner is testing one of his weapons, which the Leader or the communists are trying to steal. In the course of the theft attempt, Banner transforms into the Hulk and defeats the plot. But Banner is suspected because he's constantly disappearing. The stories tend to end with a cliffhanger which is resolved in the following issue.
Lee or Ditko did recognize that the constant suspicion on Banner would result in him being imprisoned (as he is at the end of TTA #63). So in #64, they come up with a get-out-of-jail-free card. Rick Jones (who is a member of the Avengers) gets a meeting with the President of the United States, and informs him of Banner's dual identity as the Hulk. This is a swipe from Superman, who had confided in President Kennedy (with disastrous results as I pointed out in an earlier post).
The Leader is intrigued by the Hulk's green appearance. Could he also have been transformed by Gamma rays? He resolves to kidnap him and find out.