We demonstrate that mutual gravitational interactions between an asteroid and a planet or another asteroid can play an important role in shaping an asteroid's spin state. We focus on two situations that asteroids may encounter during their lifetimes. The first is the environment after creation from a disrupted parent asteroid, when there may be many asteroid fragments interacting gravitationally with each other before their mutual escape. The other is the interaction between an asteroid and a planet during a hyperbolic flyby. In each case the mutual gravitational interaction can alter the asteroid's spin state. We derive analytical descriptions of the effects and perform numerical simulations to explore the interactions and to give examples. The net effect of many small interactions, taken in isolation, is to cause the asteroid to spin at a faster rate-although this must be balanced against all other effects that influence spin rates. Conversely, the effect of a single, strong interaction can fundamentally change an asteroid's spin state, causing it to tumble and significantly increasing or decreasing its overall angular momentum. We simulate interactions of a sphere of arbitrary mass with Toutatis and find that these types of gravitational interactions can provide partial explanations for the current Toutatis rotational state.