The filamentation instability of laser beams propagating in nonlocal nonlinear media is investigated. It is shown that the filamentation instability can occur in weakly nonlocal self-focusing media for any degree of nonlocality, and in defocusing media for the input light intensity exceeding a threshold related to the degree of nonlocality. A linear stability analysis is used to predict the initial growth rate of the instability. It is found that the nonlocality tends to suppress filamentation instability in self-focusing media and to stimulate filamentation instability in self-defocusing media. Numerical simulations confirm the results of the linear stability analysis and disclose a recurrence phenomenon in nonlocal self-focusing media analogous to the Fermi-Pasta-Ulam problem.