We investigate numerically and theoretically solitons in highly nonlocal three-dimensional nematic liquid crystals. We calculate the fundamental soliton profiles using the modified Petviashvili method. We apply the variational method to the widely accepted scalar model of beam propagation in uniaxial nematic liquid crystals and compare the results with numerical simulations. To check the stability of such solutions, we propagate them in the presence of noise. We discover that the presence of any noise induces the fundamental solitons-the so-called nematicons-to breathe. Our results explain the difficulties in experimental observation of steady nematicons. 2012 American Physical Society.