Mapping of underwater objects is usually conducted with autonomous underwater vehicles (AUVs).A standard approach in mine countermeasure (MCM) operations is to perform a two-phase reconnaissance: in the first phase, a survey mission is carried out to detect and classify the objects; in the second phase, objects are reacquired to confirm the actual presence of mines. The data acquired during this multiphase mission greatly depends on the accuracy of the AUV’s navigation system. This paper proposes a graph-based mapping algorithm that takes into account the unknown AUV position, as well as the output of the classification process, and uses the sum–product algorithm (SPA) to obtain a principled and intuitive approximation of the Bayesian inference needed for object detection and estimation. The SPA-based mapping algorithm is derived in detail, and its performance is evaluated in a simulated MCM scenario.