How do we know that it is true? Most people don't give me a very straightforward answer, but I don't like that. Lagrange must have gotten it from somwhere.
In some sense, it's a mathematical abstraction of things we already knew [like "shortest distance between two points is a line", geometric optics, Newton's laws of motion]... and we take pleasure to find that newer theories [developed after (say) Lagrange] seem to fit into this scheme... for example, quantum mechanics.
Implicit in this discussion is how one finds action that yield the equations of motion.
Back when I was an undergrad, my analytical mechanics TA briefly mentioned that the principle of least action arose from some sort of theological argument. Unfortunately I don't have any further details on that.