The paper proposes a novel Electrochemical Impedance Spectroscopy methodology that takes into account the nonlinearties present in the battery. For this purpose, the current-voltage relationship of the cell is modeled in discrete domain as a Volterra filter and the linear part of the nonlinear model is efficiently estimated using Orthogonal periodic sequences. Preliminary experimental results involving six lithium-ion cells show the soundness of the proposed approach.