In this paper, we present a new method for the estimation of the prediction-error covariances of a Kalman filter (KF), which is suitable for step-varying processes. The method uses a series of past innovations (i.e., the difference between the upcoming measurement set and the KF predicted state) to estimate the prediction-error covariance matrix by means of a constrained convex optimization problem. The latter is designed to ensure the symmetry and the positive semidefiniteness of the estimated covariance matrix, so that the KF numerical stability is guaranteed. Our proposed method is straightforward to implement and requires the setting of one parameter only, i.e., the number of past innovations to be considered. It relies on the knowledge of a linear and stationary measurement model. The ability of the method to track state step-variations is validated in ideal conditions for a random-walk process model and for the case of power-system state estimation. The proposed approach is also compared with other methods that estimate the KF stochastic parameters and with the well-known linear weighted least squares. The comparison is given in terms of both accuracy and computational time.