Localization is one of the fundamental problems in mobile robot navigation. Recent experiments showed that in general grid-based Markov localization is more robust than Kalman filtering while the latter can be more accurate than the former. In this paper we present a novel approach called Markov-Kalman localization (ML-EKF) which is a combination of both methods. ML-EKF is well suited for robots observing known landmarks, having a rough estimate of their movements, and which might be displaced to arbitrary positions at any time. Experimental results show that our method outperforms both of its underlying techniques by inheriting the accuracy of Kalman filtering and the robustness and relocalization speed of the Markov method.