Many famous problems in mathematics can be phrased as the quest for a specific construction. Often such constructions were sought after for centuries or even millennia and later proved impossible by taking a new, "higher" perspective. The most obvious example would be the three geometric problems of antiquity: squaring of circles, duplication of cubes and trisection of angles by ruler and compass alone. Closely related to these three is the construction of regular $n$-gons for general $n$. Later we have the solution of an arbitrary algebraic equation by means of radicals or the expression of the circumference of an ellipse by means of elementary functions. In the 20th century we have Hilbert's tenth problem: find an algorithm to determine whether a given diophantine equation has solutions.
All these constructions turned out to be impossible, but the futile search produced some new and great mathematics: Galois theory, group theory, transcendental numbers, elliptic curves …
But I am looking for examples which are in some sense the opposite of the above: where somebody turned up with an ingenious construction in a problem where it had been generally believed that no such construction should exist. Ideally, this construction should have made new interesting questions and methods turn up, but I am also interested in isolated results that may just be counted as funny coincidences. To make my point clearer, let me present my own two favourite examples.
(1) Belyi's Theorem: If $X$ is a smooth projective algebraic curve defined over a number field, there exists a rational function on $X$ whose only singular values are $0$, $1$ and $\infty$. — According to his Esquisse d'un programme, Grothendieck had thought about this problem shortly before but found the statement so bold that he even felt awkward for asking Deligne about it. To put the theorem into context, the converse statement (that every curve which admits a rational function with only these three singular values can be defined over a number field) had been known before by abstract nonsense and is quite straightforward to deduce from deep results in Grothendieck-style algebraic geometry. Belyi's proof, however, was completely elementary, constructive, and tricky. Also it is more important than it might seem at first sight since it opens up a very strict, and equally unexpected, connection between the topology of surfaces and number theory.
(2) Julia Robinson's theorem about the definability of integers: Suppose you want to single out $\mathbb{Z}$ as a subset of $\mathbb{Q}$, using as little structure as possible. The result in question is at least to me absolutely striking. I do not know if it was so unexpected to the experts at that time, but the construction is in any case really ingenious. It says that there exists a first-order formula $\varphi$ in the language of rings (i.e. only talking about elements, not subsets, and using only logical symbols and multiplication and addition, and the symbols $0$ and $1$) such that for a rational number $r$, $\varphi (r)$ is true if and only if $r$ is an integer. Robinson's original formula is
$$\varphi (r)\equiv\forall y\forall z(\psi (0,y,z)\wedge\forall x(\psi (x,y,z)\longrightarrow \psi (x+1,y,z))\longrightarrow\psi (r,y,z))$$
with
$$\psi (x,y,z) \equiv \exists a\exists b\exists c(2 + x^2yz = a^2 + yb^2-zc^2).$$
Since this is not my area of research I do not attempt to estimate the historical importance of this discovery, but it seems to me that it is of great weight in the intersection of number theory and logic.
So I hope these two examples make it clear what I am after, and I am looking forward to reading your examples.
Best Answer
I am not expert in the field, but it seems that Nash's embedding theorem is considered very unexpected for two reasons: first because at that time people thought that Riemannian manifolds were a so general object that nobody believed that they could be actually embedded (as smoothly as possible) in an Euclidean space. Second, because Nash's proof used new and unexpected techniques. If you read Gromov's interview for the Abel prize http://www.ams.org/notices/201003/rtx100300391p.pdf, at p.394, second column, third answer, he said: At first, I looked at one of Nash’s papers and thought it was just nonsense. But Professor Rokhlin said: “No, no. You must read it.” I still thought it was nonsense; it could not be true. But then I read it, and it was incredible. It could not be true but it was true.