  We study gray solitons in nonlocal nonlinear media and show that they are
stable and can form bound states. We reveal that gray soliton velocity depends
on the nonlocality degree, and that it can be drastically reduced in highly
nonlocal media. This is in contrast to the case of local media, where the
maximal velocity is dictated solely by the asymptotic soliton amplitude.
