The proposed implementation of a quantum annealer with ultracold Rydberg atoms in optical lattices provides a platform for adiabatic quantum computing, featuring a highly controllable environment to explore the many-body adiabatic passage, the role of entanglement and effects of decoherence during the annealing sweep. The large lifetimes of Rydberg dressed atoms enable coherent quantum annealing as an alternative to the current paradigm of quantum enhanced thermal annealing35. We anticipate that due to the coherent evolution the number of spins in future experiments can readily be extended well beyond the minimal example presented here, by using shorter annealing cycles with many repetitions36, or by employing counter-diabatic driving schemes that could greatly increase the attained fidelities7. Finally, our proposal allows to realize atomic quantum simulators of arbitrary infinite-range Ising spin glass models (see, for example, references in ref. 37), and the combination of multi-color Rydberg-dressed interactions with two-species mixtures has applications in realizing lattice gauge theories beyond the present example38.