How people reach consensus in social networks with locally distributed interactions is relevant to understanding collective group decision-making and problem-solving. However, while the importance of theory of mind in consensus problems has been hypothesized, little work has been done to test it systematically. We present both computational modeling and behavioral experiments designed to test the impact of theory of mind on individual choices within such consensus networks. We test 2,108 computational models informed by theoretical work on a graph-coloring consensus task to compare models using theory of mind to other behavioral parameters. We then use behavioral responses from 107 participants in a similar task to evaluate support for theory of mind in consensus formation. We find that the computational model that best accounts for prior behavioral data uses theory of mind, and our behavioral results likewise support use of theory of mind over other potential decision-making models.