Significant research effort has been devoted to produce one-sided error estimates for Finite Element Analyses, in particular to provide upper bounds of the actual error. Typically, this has been achieved using residual-type estimates. One of the most popular and simpler (in terms of implementation) techniques used in commercial codes is the recovery-based error estimator. This technique produces accurate estimations of the exact error but is not designed to naturally produce upper bounds of the error in energy norm. Some attempts to remedy this situation provide bounds depending on unknown constants. Here, a new step towards obtaining error bounds from the recovery-based estimates is proposed. The idea is (1) to use a locally equilibrated recovery technique to obtain an accurate estimation of the exact error, (2) to add an explicit-type error bound of the lack of equilibrium of the recovered stresses in order to guarantee a bound of the actual error and (3) to efficiently and accurately evaluate the constants appearing in the bounding expressions, thus providing asymptotic bounds. The numerical tests with h-adaptive refinement process show that the bounding property holds even for coarse meshes, providing upper bounds in practical applications.