Aside from the fact that Fermat was a genius, is it probable that he actually did have a proof?
Some specifics that I think would point one way or another:
The other answer is correct. In addition, there is significant evidence that Fermat did not have a proof of the theorem now known as Fermat's Last Theorem.
First, we should note that Fermat was not a professional mathematician, only an amateur. He never published any mathematics himself. With just that, it would not seem strange that he did not publish his proof. However, his son Samuel decided to collect Fermat's writings and letters. The famous margin which was too small for the proof was the margin of Fermat's copy of Diophantus's Arithmetica. Fermat likely wrote this note around 1630 when he first began studying this text.
From his writings and letters, we see a common trend. Almost all of the problems Fermat mentioned having solved were included in his work more than once, typically being restated as challenge problems which he then sent to various mathematicians with whom he was in correspondence. However, FLT appears only once, in this margin. It is never again mentioned in any writings that Samuel was able to find. Assuming he truly had a (long) proof which was not incorrect, he would have likely written this down or discussed it with other mathematicians, as he did with essentially every other result he found.
In fact, in his writings, we do find later references to special cases of the theorem (see Wikipedia, Proofs of Fermat's Last Theorem for specific exponents). Both the $n=3$ and $n=4$ cases are found in his later writings. It's not clear whether he knew a proof for the $n=3$ case, but if he did it was unknown at the time of his death and none was found until Euler in 1760. However, he did send multiple letters, in 1636, 1640, and 1657, containing this case as a problem. The single surviving proof by Fermat is equivalent to a proof of the $n=4$ case. It would seem very strange for him to state the problem in 1630 for all $n$, and then in much later writings, to specialize to two cases.
With this in mind, it seems there are three possibilities.
Fermat never meant to claim that he knew a proof of FLT for all $n>2$, and only wanted to state FLT as a conjecture. He may have intended to specialize to $n=3$ and/or $n=4$. This was, after all, a private writing by an amateur mathematician who was just learning number theory. It was never intended to be communicated to others, and in his communications we can find no indication of such a claim. It's not clear what he would have meant by the note in the margin.
Fermat believed he had a proof of this for all $n>2$ at the time. However, he was wrong, and very likely discovered this himself, possibly while trying to write down the proof. This would explain his later specializations to the $n=3$ and $n=4$ cases, themselves not trivial, and his decision not to communicate the result to any of the mathematicians he was in contact with. Exactly what this proof might have been is not clear. Many people since have failed to prove FLT in many ways. Being very generous, he could have made an assumption similar or somehow equivalent to one made by Lamé in his failed attempt from 1847, i.e. that $\mathbb Z[\zeta_n]$ (where $\zeta_n$ is a primitive $n$-th root of unity) has unique factorization for all $n$. Even that would have been far ahead of his time. But his error could have been something more mundane as well.
Fermat (who was just an amateur, albeit an extremely gifted one) found a correct elementary proof of FLT which has since evaded thousands of mathematicians with more sophisticated technology and more complete understanding of number theory over a period of over 350 years. He never wrote this down or communicated this result to any mathematicians, preferring to discuss only two specific cases. This can not be technically ruled out, but it seems highly unlikely, and the only evidence supporting it is a private note scribbled in the margin of a text by a man who was learning number theory for the first time.
The first two possibilities both seem reasonable, while the third is almost completely absurd. This would not be the only case in which Fermat believed he had a result which was only completely proven later. The polygonal number theorem is another major case, which was only proven by Legendre for squares in 1770, Gauss for triangles in 1796, and Cauchy in general in 1812. Gauss in particular cast some serious doubts as to whether Fermat had a proof of this. The most popular guess is possibility 2, that Fermat had some sort of argument which was flawed but perhaps worked for some small exponents. Not enough of his writings have survived to guess what that method was, and the proof he gave for $n=4$ doesn't generalize in any obvious way to other exponents.
It is simply not possible that Fermat discovered a proof which is equivalent to Wiles' proof. That would have been impossible; the concepts required to even understand Wiles' proof were not developed until the 20th century.
There is no way that Fermat could have had anything approaching the now commonly-accepted proof. Almost none of the concepts in that proof were known in any form in Fermat's time.
Further, Fermat is known for publishing very few of his proofs; almost none survive today, and even in the 1800s there was significant doubt in the mathematical community that he had proofs for much of what he stated as fact. (This is not to diminish his results; in fact, it makes it all the more impressive that his intuition led him to so many results later proved true).
From the evidence that we have, it is most likely that Fermat never even claimed to have a proof of the FLT, see the extensive discussion at Mathoverflow here. Quoting from the accepted answer:
Not only do we not know the date, we don't even know whether he wrote the remark at all. For all we know it might have been invented by his son Samuel, who published his father's comments.
In his letters, Fermat never mentioned the general case at all, but quite often posed the problem of solving the cases n=3 and n=4. I am almost certain that Fermat discovered infinite descent around 1640, which means that in 1637 he did not have any chance of proving FLT for exponent 4 (let alone in general).
