Cooperation is widespread across the tree of life, with examples ranging from vertebrates to lichens to multispecies biofilms. The initial evolution of such cooperation is likely to involve interactions that produce non-additive fitness effects among small groups of individuals in local populations. However, most models for the evolution of cooperation have focused on genealogically related individuals, assume that the factors influencing individual fitness are deterministic, that populations are very large, and that the benefits of cooperation increase linearly with the number of cooperative interactions. Here we show that stochasticity and non-additive interactions can facilitate the evolution of cooperation in small local groups. We derive a generalized model for the evolution of cooperation and show that if cooperation reduces the variance in individual fitness (separate from its effect on average fitness), this can aid in the evolution of cooperation through directional stochastic effects. In addition, we show that the potential for the evolution of cooperation is influenced by non-additivity in benefits with cooperation being more likely to evolve when the marginal benefit of a cooperative act increases with the number of such acts. Our model compliments traditional cooperation models (kin selection, reciprocal cooperation, green beard effect, etc.) and applies to a broad range of cooperative interactions seen in nature.