His work on brownian motion showed that the observations of the movements of small particles can be explained by the nature of fluids as being made up of small particles (i.e. molecules).

Special relativity is what you get when you combine the seemingly contradictory observed phenomena that there's no such thing as absolute motion and that the speed of light is a constant to all observers.

General relativity combines that with the observed phenomenon of gravity.

While I don't know whether these constitute "proof," Einstein certainly had a lot of empirical support for his ideas, and they weren't anything like pure intuition.