In battery-electric vehicles, an accurate knowledge of the current state of charge (SOC) of the battery is crucial for safe and efficient operation. Offset-free SOC estimation for Lithium-ion batteries (LIB) during operation still is a challenging problem, due to the uncertain output nonlinearity present in battery models. In battery management systems employed in such vehicles, the age- and cycle-dependent relationship between the open circuit voltage (OCV) and the state of charge of each cell (SOC) can be kept track of using lookup tables. Between the scattered data points, linear interpolation is often used. Another common approach is to switch between models, each with a different piecewise polynomial fit of low order. In this contribution, a single polynomial fit of a higher order with state-dependent coefficients for the whole SOC-OCV range is proposed, so as to avoid switching and facilitate usage of Taylor-based linearization algorithms like in the extended Kalman filter. While the polynomial order is high, the number of parameters is only three; the parameters are estimated and updated by the Kalman filter itself. This augmentation of the observer's state vector with said polynomial parameters is inspired by the idea of an increased “stochastization,” introducing redundancy that aids to achieve a more accurate SOC estimation. In this sense, the algorithm can be described as a model-adaptive extended Kalman estimator. Two variants of a polynomial EKF are investigated: polynomial EKF with output and with state nonlinearity models. Their performances are compared in real experiments using a dedicated test bench based on a Samsung ICR18650-26F cell, demonstrating the effectiveness of the algorithms. The variant that includes the terminal voltage in the state vector, i.e. the state nonlinearity variant of the EKF, shows better result, also compared to the existing literature.