Background: During the COVID-19 pandemic, much misinformation and disinformation emerged and spread rapidly via the internet, posing a severe public health challenge. While the need for eHealth literacy (eHL) has been emphasized, few studies have compared the difficulties involved in seeking and using COVID-19 information between adult internet users with low or high eHL. Objective: This study examines the association between eHL and web-based health information–seeking behaviors among adult Japanese internet users. Moreover, this study qualitatively shed light on the difficulties encountered in seeking and using this information and examined its relationship with eHL. Methods: This cross-sectional internet-based survey (October 2021) collected data from 6000 adult internet users who were equally divided into sample groups by gender, age, and income. We used the Japanese version of the eHL Scale (eHEALS). We also used a Digital Health Literacy Instrument (DHLI) adapted to the COVID-19 pandemic to assess eHL after we translated it to Japanese. Web-based health information–seeking behaviors were assessed by using a 10-item list of web sources and evaluating 10 topics participants searched for regarding COVID-19. Sociodemographic and other factors (eg, health-related behavior) were selected as covariates. Furthermore, we qualitatively explored the difficulties in information seeking and using. The descriptive contents of the responses regarding difficulties in seeking and using COVID-19 information were analyzed using an inductive qualitative content analysis approach. Results: Participants with high eHEALS and DHLI scores on information searching, adding self-generated information, evaluating reliability, determining relevance, and operational skills were more likely to use all web sources of information about COVID-19 than those with low scores. However, there were negative associations between navigation skills and privacy protection scores when using several information sources, such as YouTube (Google LLC), to search for COVID-19 information. While half of the participants reported no difficulty seeking and using COVID-19 information, participants who reported any difficulties,including information discernment, incomprehensible information, information overload, and disinformation, had lower DHLI score. Participants expressed significant concerns regarding "information quality and credibility," "abundance and shortage of relevant information," "public trust and skepticism," and "credibility of COVID-19-related information." Additionally, they disclosed more specific concerns, including "privacy and security concerns," "information retrieval challenges," "anxieties and panic," and "movement restriction." Conclusions: Although Japanese internet users with higher eHEALS and total DHLI scores were more actively using various web sources for COVID-19 information, those with high navigation skills and privacy protection used web-based information about COVID-19 cautiously compared with those with lower proficiency. The study also highlighted an increased need for information discernment when using social networking sites in the "Health 2.0" era. The identified categories and themes from the qualitative content analysis, such as "information quality and credibility," suggest a framework for addressing the myriad challenges anticipated in future infodemics.