A curve fitting is the most important process in the analysis of electrochemical impedance spectra to evaluate the ionic conductivity of materials. To analyze the impedance spectra, a gradient method such as steepest descent has been used so far. However, the parameter solution by using the gradient method is often trapped into local minima, and the curve fitting strongly depends on the initial parameters. In this study, to avoid the local minima issue, we propose a random walk Metropolis Hastings algorithm to analyze impedance spectra, where we can provide a unique solution of the impedance spectra. As an example, we measured the solid-state oxide electrolyte of (La0.62Li0.15)TiO3, (La0.53Li0.40)TiO3 and (La0.31Li0.07)NbO3 polycrystal and we uniquely identify the respective lithium ion conductivity at the bulk and the grain boundary by using the random walk Metropolis Hastings algorithm. The present algorithm is free from the choice of the initial values of the fitting parameters and moreover the estimated accuracy of the Li-ion conductivity is better than 5%.