Einstein won his Nobel Prize for explaining the photoelectric effect, a measured phenomenon that didn't have an adequate explanation.
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.
Einstein's idea of "intuition" is bastardized sometimes. He didn't mean "Having a common-sense opinion that something is wrong or right" as intuition, he just meant "Think really hard about the underlying principles and reach a conclusion", as opposed to "Make an arbitrary mathematical model, try to fit the data, iterate".
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.