In many environmental management problems, the construction of occurrence maps of species of interest is a prerequisite to their effective management. However, the construction of occurrence maps is a challenging problem because observations are often costly to obtain (thus incomplete) and noisy (thus imperfect). It is therefore critical to develop tools for designing efficient spatial sampling strategies and for addressing data uncertainty. Adaptive sampling strategies are known to be more efficient than non-adaptive strategies. Here, we develop a model-based adaptive spatial sampling method for the construction of occurrence maps. We apply the method to estimate the occurrence of one of the world’s worst invasive species, the red imported fire ant, in and around the city of Brisbane, Australia. Our contribution is threefold: (i) a model of uncertainty about invasion maps using the classical image analysis probabilistic framework of Hidden Markov Random Fields (HMRF), (ii) an original exact method for optimal spatial sampling with HMRF and approximate solution algorithms for this problem, both in the static and adaptive sampling cases, (iii) an empirical evaluation of these methods on simulated problems inspired by the fire ants case study. Our analysis demonstrates that the adaptive strategy can lead to substantial improvement in occurrence mapping.