In Bayesian statistics, exploring high-dimensional multimodal posterior distributions poses major challenges for existing MCMC approaches. This paper introduces the Annealed Leap-Point Sampler (ALPS), which augments the target distribution state space with modified annealed (cooled) distributions, in contrast to traditional tempering approaches. The coldest state is chosen such that its annealed density is well-approximated locally by a Laplace approximation. This allows for automated setup of a scalable mode-leaping independence sampler. ALPS requires an exploration component to search for the mode locations, which can either be run adaptively in parallel to improve these mode-jumping proposals, or else as a pre-computation step. A theoretical analysis shows that for a d-dimensional problem the coolest temperature level required only needs to be linear in dimension, {}mathcal{O}(d) implying that the number of iterations needed for ALPS to converge is {}mathcal{O}(d) (typically leading to overall complexity {}mathcal{O}(d^3) when computational cost per iteration is taken into account). ALPS is illustrated on several complex, multimodal distributions that arise from real-world applications. This includes a seemingly-unrelated regression (SUR) model of longitudinal data from U.S. manufacturing firms, as well as a spectral density model that is used in analytical chemistry for identification of molecular biomarkers.