In this study, novel solutions to Global Urban Localization problem is proposed and examined rigorously. Classical approaches including Particle Filter, mixture of Gaussians, as well as novel solutions like Viterbi Algorithm and differential evolution are evaluated. The contribution of this paper is twofold: The Viterbi algorithm is extended by exploiting the structure of the problem at hand that is the states are partially connected temporally. Differential evolution is modified by taking into account the covariance matrix of states. Thus states encoded in genes are only allowed to interact locally within the region described by covariance matrix. This prevents the differential evolution from getting trapped into false maxima in the early stages of optimization. Finally, it is demonstrated with extensive experiments that solution of Global Urban Localization problem is possible. (C) 2009 Elsevier B.V. All rights reserved.