We introduce the Marco Polo localization approach, where we apply sound as a tool for gathering range measurements between robots, and use those to solve a range-only simultaneous localization and mapping problem. Range is calculated by correlating two recordings of the same sound, recorded on a pair of robots, after which the resulting time delay estimate is converted to a range measurement. The algorithmic approach we use is a straightforward application of the Bayesian estimation framework. We also present two complementary views on the associated optimization problem that provide insight into the problem and allows one to devise initialization strategies, indispensable in a range-only scenario. We illustrate the approach with both simulated and experimental results.