The effect of negatively charged dust on the Kelvin-Helmholtz (parallel velocity shear) instability is investigated experimentally in a magnetized cesium plasma. The dust generally has a stabilizing effect on the instability, although, in some cases, the addition of negatively charged dust into the plasma results in a slight increase in the instability fluctuation amplitude. The results are in general agreement with theoretical predictions. (C) 2001 American Institute of Physics. [DOI: 10.1063/1.1323755].