Background Timely and effective contact tracing is an essential public health measure for curbing the transmission of COVID-19. App-based contact tracing has the potential to optimize the resources of overstretched public health departments. However, its efficiency is dependent on widespread adoption. Objective This study aimed to investigate the uptake of the Australian Government’s COVIDSafe app among Australians and examine the reasons why some Australians have not downloaded the app. Methods An online national survey, with representative quotas for age and gender, was conducted between May 8 and May 11, 2020. Participants were excluded if they were a health care professional or had been tested for COVID-19. Results Of the 1802 potential participants contacted, 289 (16.0%) were excluded prior to completing the survey, 13 (0.7%) declined, and 1500 (83.2%) participated in the survey. Of the 1500 survey participants, 37.3% (n=560) had downloaded the COVIDSafe app, 18.7% (n=280) intended to do so, 27.7% (n=416) refused to do so, and 16.3% (n=244) were undecided. Equally proportioned reasons for not downloading the app included privacy (165/660, 25.0%) and technical concerns (159/660, 24.1%). Other reasons included the belief that social distancing was sufficient and the app was unnecessary (111/660, 16.8%), distrust in the government (73/660, 11.1%), and other miscellaneous responses (eg, apathy and following the decisions of others) (73/660, 11.1%). In addition, knowledge about COVIDSafe varied among participants, as some were confused about its purpose and capabilities. Conclusions For the COVIDSafe app to be accepted by the public and used correctly, public health messages need to address the concerns of citizens, specifically privacy, data storage, and technical capabilities. Understanding the specific barriers preventing the uptake of contact tracing apps provides the opportunity to design targeted communication strategies aimed at strengthening public health initiatives, such as downloading and correctly using contact tracing apps.