The influence of potential dependent relative permittivity of Stern layer on the capacitance of electrode-electrolyte interface is studied theoretically. A decrease of capacitance at larger magnitudes of electrode surface potential is predicted. At large electrode surface potentials the capacitance of metal-electrolyte interface is determined solely by the capacitance of Stern layer, whereas the contribution of the capacitance of diffuse layer is negligible.