Background: Downloading a COVID-19 contact tracing app may be effective in reducing users’ worry about COVID-19 and psychological distress. Objective: This 2.5-month prospective study aimed to investigate the association of downloading a COVID-19 contact tracing app, the COVID-19 Contact Confirming Application (COCOA), released by the Japanese government, with worry about COVID-19 and psychological distress in a sample of employed adults in Japan. Methods: A total of 996 full-time employed respondents to an online survey conducted May 22-26, 2020 (baseline), were invited to participate in a follow-up survey August 7-12, 2020 (follow-up). A high level of worrying about COVID-19 and high psychological distress were defined by baseline and follow-up scores on a single-item scale and the Kessler 6 (K6) scale, respectively. The app was released between the two surveys, on June 17. Participants were asked at follow-up if they downloaded the app. Results: A total of 902 (90.6%) of 996 baseline participants responded to the follow-up survey. Among them, 184 (20.4%) reported that they downloaded the app. Downloading of the contact tracing app was significantly negatively associated with psychological distress at follow-up after controlling for baseline variables, but not with worry about COVID-19. Conclusions: This study provides the first evidence that using a government-issued COVID-19 contact tracing app may be beneficial for the mental health of employed adults during the COVID-19 pandemic.