In this paper we will apply interval methods to solve the problem of robust localization of an underwater robot. The localization problem is cast into a constraint satisfaction problem (CSP) where constraint propagation algorithms are particularly efficient. The method is designed to work in real environments with numerous outliers. Besides, we used a new approach to represent the map by a binary image. This allow us to represent even unstructured maps. We tested the algorithm on a real data set gathered by an underwater robot in a marina located in Costa Brava.