Experimental mathematics leading to major advances

Computer experiments (in the early 1960s!) led Birch and Swinnerton-Dyer to the formulation of their conjecture, which stimulated the development of much of arithmetic geometry.

The Prime Number Theorem was conjectured by Gauss from looking (very hard, one can presume...) at a table of the primes $\leq10^6$. It is not with too much effort that one can read his Disquisitiones as a set of tricks to determine primality with as little work as possible, and one can understand the motivation: he was his own computer, in a way :P

(I don't know where Legendre got the statement from, but he must surely have had tables of primes too!)

A lot of Rich Schwartz's work begins with computer experiments.

Perhaps most notably is his proof that a triangle whose largest angle is less than 100 degrees has a periodic billiard trajectory.