Conservation of energy is a property that a particular physical system may have. Most often, one determines if a system conserves energy by studying the symmetries of the Lagrangian. As others have said, conservation of energy is associated with the Lagrangian being symmetric in time.
But there is no a priori reason that all possible Lagrangians conserve energy. For example, consider the Lagrangian of the universe. The universe, as we now know, is expanding, meaning it is certainly changing as a function of time. Thus, on a very global scale, the energy of the universe isn't conserved. But this applies to only the very largest of scales. Locally, we don't notice the expansion of the universe, and energy is conserved to excellent precision.
But, taking a step back, saying that conservation of energy can be derived from a symmetry of the Lagrangian is a bit of a circular argument. If you write down a Lagrangian that is invariant under time symmetry, then you can define an energy that doesn't change in time. That's true.
But I guess none of this yet answers your question, which was "On what basis do we trust conservation of energy." The answer to that is the vast experimental evidence, from day-to-day experiences to precision physical measurements. Based on experiment, our local laws of physics don't change as a function of time.