Examples where existence is harder than evaluation

The Prime Number Theorem.

Chebyshev proved that if $$\lim_{n\to\infty}{\pi(n)\log n\over n}$$ exists (here, $\pi(n)$ is the number of primes up to $n$), then it equals $1$. Fifty years passed after that before Hadamard and de la Vallée Poussin (independently) proved that the limit exists.

Brownian motion is an example of this phenomenon in probability.

I am no expert on the history, but Einstein is often credited with having described, in 1905, the mathematical properties that Brownian motion ought to have: a continuous process with independent increments whose distribution at time $t$ is Gaussian with variance proportional to $t$. (It seems that Bachelier may have also done it independently in 1900.) These properties uniquely define Brownian motion (up to scaling), and so any question you may have about Brownian motion can in principle be deduced from these axioms. For instance, you can compute its quadratic variation, and show that it is a Markov process and a martingale, and define and compute stochastic integrals, and so on.

But proving that there actually exists a process with these properties is harder. Historically, it took another 18 years or so before this was done (by Wiener in 1923).

(From Wiener's point of view, the object in question is a measure on the Banach space $C([0,1])$; the aforementioned properties tell us the finite-dimensional projections of this measure, which would uniquely determine it; but it is not trivial to prove the existence of a measure with those projections.)

(The historical notes are from Pitman and Yor, Guide to Brownian Motion, which see for more references.)

Isoperimetric problem. Using clever geometric argument Steiner proved in 1838 that if there is a geometric figure of the highest area for a given perimeter, it must be a circle. However, it was only Blaschke in 1919 who showed the existence of such a figure.

By the way, Aknazar Kazhymurat's answer is approximately the Perron's joke about invalidity of Steiner's proof.