Electrochemical Impedance Spectroscopy (EIS) and Equivalent Circuit Models (ECMs) are widely used to characterize the impedance and estimate parameters of electrochemical systems such as batteries. We use a generic ECM with ten parameters grouped to model different frequency regions of the Li-ion cell’s impedance spectrum. We derive a noise covariance matrix from the measurement model and use it to assign weights for the fitting technique. The paper presents two formulations of the parameters identification problem. Using the properties of the ECM EIS spectra, we propose a method to initialize ECM parameters for the Complex Non-linear Least Squares (CNLS) technique. The paper proposes a novel algorithm for designing the EIS experiments by applying the theory on Cramér-Rao Lower Bound (CRLB) and Fisher Information Matrix (FIM) to the identification problem. We show that contributions to the FIM elements strongly depend on the frequencies at which EIS is performed. Hence, the algorithm aims to adjust frequencies such that the most information about parameters is collected. This is done by minimizing the highest variance of ECM parameters defined by CRLB. Results of a numerical experiment show that the estimator is efficient, and frequency adjustment leads to more accurate ECM parameters’ identification.