Incoherent optical spatial solitons are self-trapped beams with a multimodal structure that varies randomly in time. They form when their diffraction-broadening, which is governed by their spatial correlations, is balanced by nonlinear interaction between the waves and the medium, resulting in the stationary propagation of the time-averaged intensity structure of the beam. The experimental observation of incoherent solitons has opened up exciting new avenues in soliton science. However, all incoherent spatial solitons observed to date have been supported by nonlinearities with a slow response time, τ, that is much longer than the characteristic fluctuation time of the beam, t_c ≪ τ. Here, we demonstrate incoherent solitons in effectively instantaneous nonlocal nonlinear media where τ ≪ t_c. These solitons exhibit fundamentally new features (for example, propagation at random trajectories), and can be created in various optically nonlinear media, as well as in other fields where the nonlinearity is nonlocal and very fast.