As safety and reliability critical components, lithium-ion batteries always require real-time diagnosis and prognosis. This often involves a large amount of computation, which makes diagnosis and prognosis difficult to implement, especially in embedded or mobile applications. To address this issue, this paper proposes a run-time Reconfigurable Computing (RC) system on Field Programmable Gate Array (FPGA) for Relevance Vector Machine (RVM) to realize real-time Remaining Useful Life (RUL) estimation. The system leverages state-of-the-art run-time dynamic partial reconfiguration technology and customized computing circuits to balance the hardware occupation and computing efficiency. Optimal hardware resource consumption is achieved by partitioning the RVM algorithm according to a multi-objective optimization. Moreover, pipelined and parallel computation circuits for kernel function and matrix inverse are proposed on FPGA to further accelerate the computation. Experimental results with two different battery data sets show that, without sacrificing the RUL prediction performance, the embedded RC platform significantly reduces the computation time and the requirement of hardware resources. This demonstrates that complex prognostic tasks can be implemented and deployed on the proposed system, and it can be extended to the embedded computation of other machine learning algorithms.