In recent years, the use of lithium-ion batteries in smart-grids and hybrid/electric vehicles has become increasingly popular because they provide a flexible and cost-effective way to store and deliver energy. Their full integration into more complex systems requires an accurate estimate of the energy a battery is currently storing, i.e., the State of Charge (SoC). However, standard techniques in the literature provide an accurate estimate of the SoC by having only a priori knowledge of the battery. Moreover, their accuracy decreases if the battery’s operating conditions (e.g., outdoor temperature) vary over time or if the battery measurements required for SoC estimation are affected by measurement errors. To overcome these limitations, this paper proposes a new data-driven methodology, called VDB-SE, for battery SoC estimation. The proposed methodology provides accurate SoC estimates without knowing battery model parameters such as capacitance and internal resistance, the characterization of which would require complex and time-consuming laboratory tests. Experimental verification and comparisons show that the performance of VDB-SE is comparable to state-of-the-art algorithms for various working conditions. In fact, the difference in performance is less than 0.2%. Furthermore, experimental results showed that on a real energy storage system, the proposed method provides an estimate of the SoC with an error of less than 2.1%.