At it's very basic level, e=mc^2 just shows that when you measure the mass of something, you are in fact measuring its energy and vice versa.
So all energy has mass, and all mass has energy and you can convert between them using this formula.
The relationship is simple and while others had postulated some link between the two before, it's not an obvious one (e.g why it should necessarily be so).
(You may ask about photons not having any mass but yet having energy, but then e^2= p^2*c^2 + m^2*c^4 doesn't have the same ring 
).