Aside from his conversations with Jordan Baker, who knows quite a bit about Daisy's past and with that about Gatsby, Nick is suspicious of the manner in which Gatsby speaks, and of certain "tells" that seem to indicate untruths:
He looked at me sideways -- and I knew why Jordan Baker had believed he was lying. He hurried the phrase "educated at Oxford," or swallowed it, or choked on it, as though it had bothered him before. And with this doubt, his whole statement fell to pieces...
(Fitzgerald, The Great Gatsby, mrbye.com)
It is Gatsby's own unease with his fabricated past that gives him away. If he were to be calmer and speak with slow simplicity, he would likely have no trouble convincing people of his origins. However, since he "chokes" on the phrase "educated at Oxford," Nick suspects that part of his story. Gatsby is playing the part of an "Old Money" heir, but cannot pull it off in front of people familiar with that sort of persona. The single seed of doubt taints everything else he says, until Nick is personally unsure of Gatsby's life or the truth behind his actions; he is therefore not wholly surprised later when he discovers how Gatsby rose to wealth.