In this paper we propose a novel approach to localization in very large indoor spaces (i.e., shopping malls with over 200 stores) that takes a single image and a floor plan of the environment as input. We formulate the localization problem as inference in a Markov random field, which jointly reasons about text detection (localizing shop names in the image with precise bounding boxes), shop facade segmentation, as well as camera’s rotation and translation within the entire shopping mall. The power of our approach is that it does not use any prior information about appearance and instead exploits text detections corresponding to shop names as a cue for localization. This makes our method applicable to a variety of domains and robust to store appearance variation across countries, seasons, and illumination conditions. We demonstrate our approach on our new dataset spanning two very large shopping malls, and show the power of holistic reasoning.