His starting point was to realize that Newton's gravity didn't satisfy his principles of the (special) theory of relativity because it wasn't Lorentz-invariant and it included action at a distance, faster-than-light effects of gravity that could spread immediately.
So he was looking for a better theory that would be compatible with the principles of relativity. It took him a decade after special relativity was found to find and complete general relativity. Let me completely skip dead ends he had tried although these stories are interesting and one could learn something from them, too. At some point in 1911, in Prague's Viničná Street (see some letters Einstein wrote about Prague), he realized that the equivalence principle was a very special property of gravity – known already to Galileo but not appreciated as an important principle – and it led his final years.
Eventually he realized that the spacetime had to be curved, by arguments based on the equivalence principle, and it must be described by the Riemannian geometry. He was looking for the right equations that could relate the curvature of spacetime and the density of matter in the spacetime and finally in 1915, he found his Einstein's equations.
I think that he found the equations in their explicit form and the Einstein-Hilbert action from which the equations may be derived via the principle of least action were found later – also independently by Hilbert. We may say that the principle of least action wasn't necessary to discover GR; the equivalence principle was essential but Einstein needed (and one needs) more insights than just this principle.