Background: The implementation of an integrated electronic health record (EHR) system can potentially provide health care providers with support standardization of patient care, pathways, and workflows, as well as provide medical staff with decision support, easier access, and the same interface across features and subsystems. These potentials require an implementation process in which the expectations of the medical staff and the provider of the new system are aligned with respect to the medical staff's knowledge and skills, as well as the interface and performance of the system. Awareness of the medical staff's level of eHealth literacy may be a way of understanding and aligning these expectations and following the progression of the implementation process. Objective: The objective of this study was to investigate how a newly developed and modified instrument measuring the medical staff's eHealth literacy (staff eHealth Literacy Questionnaire [eHLQ]) can be used to inform the system provider and the health care organization in the implementation process and evaluate whether the medical staff's perceptions of the ease of use change and how this may be related to their level of eHealth literacy. Methods: A modified version of the eHLQ was distributed to the staff of a medical department in Denmark before and 3 months after the implementation of a new EHR system. The survey also included questions related to users' perceived ease of use and their self-reported information technology skills. Results: The mean age of the 194 participants before implementation was 43.1 (SD 12.4) years, and for the 198 participants after implementation, it was 42.3 (SD 12.5) years. After the implementation, the only difference compared with the preimplementation data was a small decrease in staff eHLQ5 (motivated to engage with digital services; unpaired 2-tailed t test; P = .009; effect size 0.267), and the values of the scales relating to the medical staff's knowledge and skills (eHLQ1-3) were approximately ≥3 both before and after implementation. The range of scores was narrower after implementation, indicating that some of those with the lowest ability benefited from the training and new experiences with the EHR. There was an association between perceived ease of use and the 3 tested staff eHLQ scales, both before and after implementation. Conclusions: The staff eHLQ may be a good candidate for monitoring the medical staff's digital competence in and response to the implementation of new digital solutions. This may enable those responsible for the implementation to tailor efforts to the specific needs of segments of users and inform them if the process is not going according to plan with respect to the staff's information technology-related knowledge and skills, trust in data security, motivation, and experience of a coherent system that suits their needs and supports the workflows and data availability.