A method and apparatus for robust localization in outdoor environments is provided. The localization method includes the steps of receiving scanner data from localization means and receiving angle information of a mobile device from an angle sensor, correcting the scanner data based on the received angle information, performing an Iterative Closest Point (ICP) mechanism for the corrected scanner data and generating a first constraint, and localizing the mobile device based on a graph structure under the first constraint.