Many open questions surround the processes that led to the evolutionary origin of mutualism between hosts and endosymbionts. In particular, large effect size mutations and coevolution have both been hypothesized to be important. Here we conduct in silico experiments using the Symbulation platform to explore these questions. We find that increasing mutation size and mutation rate both promote the evolution of mutualism, as does faster generational turnover within symbionts. Our results support the idea that large effect size mutations are important for the de novo evolution of mutualism. Indeed, follow-up mathematical modeling suggests that large regions of the parameter space where mutualism evolves can be explained purely by mutation size and rate. However, we observe that mutualism evolves in a wider region of parameter space than we would expect under this simple probabilistic model. We hypothesize that coevolutionary forces are responsible for this discrepancy, a hypothesis that is further corroborated by phylogenetic data showing that partners in the first mutualism are often themselves descended from mutualists. Ultimateley, we conclude that both mutation size and coevolution play a role in the evolution of mutualism. We anticipate that our findings will generalize to other systems featuring evolution along the parasitism-mutualism spectrum. Our work furthers efforts to predict host-endosymbiont coevolution.