Background: The coronavirus disease (COVID-19) has led to dramatic changes worldwide in people’s everyday lives. To combat the pandemic, many governments have implemented social distancing, quarantine, and stay-at-home orders. There is limited research on the impact of such extreme measures on mental health. Objective: The goal of this study was to examine whether stay-at-home orders produced differential changes in mental health symptoms using internet search queries on a national scale. Methods: In the United States, individual states vary in their adoption of measures to reduce the spread of COVID-19; as of March 23, 2020, 11 of the 50 states had issued stay-at-home orders. The staggered rollout of stay-at-home measures across the United States allows us to investigate whether these measures impact mental health by exploring variations in mental health search queries across the states. This paper examines the changes in mental health search queries on Google between March 16-23, 2020, across each state and Washington, DC. Specifically, this paper examines differential changes in mental health searches based on patterns of search activity following issuance of stay-at-home orders in these states compared to all other states. The participants were all the people who searched mental health terms in Google between March 16-23. Between March 16-23, 11 states underwent stay-at-home orders to prevent the transmission of COVID-19. Outcomes included search terms measuring anxiety, depression, obsessive-compulsive, negative thoughts, irritability, fatigue, anhedonia, concentration, insomnia, and suicidal ideation. Results: Analyzing over 10 million search queries using generalized additive mixed models, the results suggested that the implementation of stay-at-home orders are associated with a significant flattening of the curve for searches for suicidal ideation, anxiety, negative thoughts, and sleep disturbances, with the most prominent flattening associated with suicidal ideation and anxiety. Conclusions: These results suggest that, despite decreased social contact, mental health search queries increased rapidly prior to the issuance of stay-at-home orders, and these changes dissipated following the announcement and enactment of these orders. Although more research is needed to examine sustained effects, these results suggest mental health symptoms were associated with an immediate leveling off following the issuance of stay-at-home orders.