Heegner's solution to the Gauss class number 1 problem for imaginary quadratic fields, by noting that when the class number is 1 then a certain elliptic curve is defined over Q and certain modular functions take integer values at certain quadratic irrationalities, and then finding all the solutions to Diophantine equations that result, seems to me equally beautiful and unexpected. Maybe its unexpectedness kept people from believing it for a long time.