We observed and controlled the Brownian motion of solitons. We launched solitonic excitations in highly elongated Rb-87 Bose-Einstein condensates (BECs) and showed that a dilute background of impurity atoms in a different internal state dramatically affects the soliton. With no impurities and in one dimension (1D), these solitons would have an infinite lifetime, a consequence of integrability. In our experiment, the added impurities scatter off the much larger soliton, contributing to its Brownian motion and decreasing its lifetime. We describe the soliton s diffusive behavior using a quasi-1D scattering theory of impurity atoms interacting with a soliton, giving diffusion coefficients consistent with experiment.