The areas we term physics today have had a strong relationship to mathematics for as long as we have history about their study. Archimedes of Ancient Greece is well known for describing the law of levers in his On the Equilibrium of Planes. While the language for describing the mathematics has changed over the centuries, the use of math as a tool of physics is fairly persistent throughout recorded history.

That relationship with mathematics deepened quite dramatically when Newtonian mechanics came around. For really the first time, there was a well-defined system utilizing powerful new mathematical techniques that gained wide acceptance and completely deterministic. However, longstanding issues with math itself remained to be solved. The existence of irrational numbers had long-since been accepted in Europe by the time of Newton. However, they raised minor issues about the stability of calculations. The real issues would come out as people looked deeper into mechanics and realized that they led back to age-old questions. The most thorny of these questions were roots of polynomial equations. Until the 16th century, there were no methods for solving general polynomials higher than degree 4, but the proof of impossibility remained undiscovered. When one was finally released in 1824, it cemented the idea that physics is not quite as deterministic as some had claimed. Some scenarios under mechanics were quite literally unsolvable. These mathematical crises continued up through the end of the 19th century and physics began to diverge from the idea of deterministic models. The situation changed quite rapidly with the exploration of quantum mechanics and atomic theory. As statistical models became more advanced, a different sort of determinism emerged. You could talk about the probabilities of events as well as you could talk as "normal predictions" before, but they remained probabilities. At nearly the same time, Einsteinian relativity was coming into focus. His General Relativity brought the relatively new and obscure field of differential geometry into the academic limelight. Research during WWII led to significant collaboration between physicists and mathematicians, greatly influencing academics in both subjects. Much of the closeness we see today between theoretical physics and math came as a result of these later collaborations and both subjects have recognized the important contributions of others to them.

I don't want to go on too long about this subject because I can go on for hours about it. To answer your questions more quickly (and directly!), physics and math have always been related. The other physical sciences like Chemistry were not related on more than a superficial level until much later. Even today, parts of biology are undergoing a quiet transition towards the integration of more mathematics. But the utility of mathematics isn't really in the simplicity of the equations. There has been a lot of discussion over the roles of simplicity vs elegance in mathematics, which is a surprisingly subtle issue. Generally, the physics community has come to the consensus that elegant models with as much simplicity as possible are the best solutions. But elegance and simplicity are still considered very weak evidence for a model. Empirical verification is by far the most highly regarded form of evidence by all but the rather odd denizens of the back offices of your local theoretical physics department.