System states are related, directly or indirectly, to health condition indicators. Indeed, critical system failures can be efficiently characterized through a state space manifold. This fact has encouraged the development of a series of failure prognostic frameworks based on Bayesian processors (e.g. particle or unscented Kalman filters), which efficiently help to estimate the Time-of-Failure (ToF) probability distribution in nonlinear, non- Gaussian, systems with uncertain future operating profiles. However, it is still unclear how to determine the efficacy of these methods, since the Prognostics and Health Management (PHM) community has not developed rigorous theoretical frameworks that could help to define proper performance indicators. In this regard, this article introduces novel prognostic performance metric based on the concept of Bayesian Cramér-Rao Lower Bounds (BCRLBs) for the predicted state mean square error (MSE), which is conditional to measurement data and model dynamics; providing a formal mathematical definition of the prognostic problem. Furthermore, we propose a novel step-by-step design methodology to tune prognostic algorithm hyper-parameters, which allows to guarantee that obtained results do not violate fundamental precision bounds. As an illustrative example, both the predictive BCRLB concept and the proposed design methodology are applied to the problem of End-of-Discharge (EoD) time prognostics in lithium-ion batteries.