We evaluate the Brownian motion of a massive particle ("black hole") at the center of a galaxy using N-body simulations. Our galaxy models have power-law central density cusps like those observed at the centers of elliptical galaxies. The simulations show that the black hole achieves a steady-state kinetic energy that is substantially different than would be predicted based on the properties of the galaxy model in the absence of the black hole. The reason appears to be that the black hole responds to stars whose velocities have themselves been raised by the presence of the black hole. Over a wide range of density slopes and black hole masses, the black hole's mean kinetic energy is equal to what would be predicted under the assumption that it is in energy equipartition with stars lying within a distance ~r_h/2 from it, where r_h is the black hole's influence radius. The dependence of the Brownian velocity on black hole mass is approximately <V^2>~ 1/M^{1/(3-gamma)} with gamma the power-law index of the stellar density profile, rho~1/r^gamma. This is less steep than the 1/M dependence predicted in a model where the effect of the black hole on the stellar velocities is ignored. The influence of a stellar mass spectrum on the black hole's Brownian motion is also evaluated and found to be consistent with predictions from Chandrasekhar's theory. We use these results to derive a probability function for the mass of the Milky Way black hole based on a measurement of its proper motion velocity. Interesting constraints on M will require a velocity resolution exceeding 0.5 km/s.