The coherence of waves in periodic systems (lattices) is crucial to their dynamics, as interference effects, such as Bragg reflections, largely determine their propagation. Whereas linear systems allow superposition, nonlinearity introduces a non-trivial interplay between localization effects, coupling between lattice sites, and incoherence. Until recently, all research on solitary waves (solitons) in nonlinear lattices has involved only coherent waves. In such cases, linear dispersion or diffraction of wave packets can be balanced by nonlinear effects, resulting in coherent lattice (or 'discrete') solitons; these have been studied in many branches of science. However, in most natural systems, waves with only partial coherence are more common, because fluctuations (thermal, quantum or some other) can reduce the correlation length to a distance comparable to the lattice spacing. Such systems should support random-phase lattice solitons displaying distinct features. Here we report the experimental observation of randomphase lattice solitons, demonstrating their self-trapping and local periodicity in real space, in addition to their multi-peaked power spectrum in momentum space. We discuss the relevance of such solitons to other nonlinear periodic systems in which fluctuating waves propagate, such as atomic systems, plasmas and molecular chains.