Background: Although the persistence of physical symptoms after SARS-CoV-2 infection is a major public health concern, evidence from large observational studies beyond one year post diagnosis remain scarce. We aimed to assess the prevalence of physical symptoms in relation to acute illness severity up to more than 2-years after diagnosis of COVID-19. Methods: This multinational study included 64,880 adult participants from Iceland, Sweden, Denmark, and Norway with self-reported data on COVID-19 and physical symptoms from April 2020 to August 2022. We compared the prevalence of 15 physical symptoms, measured by the Patient Health Questionnaire (PHQ-15), among individuals with or without a confirmed COVID-19 diagnosis, by acute illness severity, and by time since diagnosis. We additionally assessed the change in symptoms in a subset of Swedish adults with repeated measures, before and after COVID-19 diagnosis. Findings: During up to 27 months of follow-up, 34.5% participants (22,382/64,880) were diagnosed with COVID-19. Individuals who were diagnosed with COVID-19, compared to those not diagnosed, had an overall 37% higher prevalence of severe physical symptom burden (PHQ-15 score ≥15, adjusted prevalence ratio [PR] 1.37 [95% confidence interval [CI] 1.23–1.52]). The prevalence was associated with acute COVID-19 severity: individuals bedridden for seven days or longer presented with the highest prevalence (PR 2.25 [1.85–2.74]), while individuals never bedridden presented with similar prevalence as individuals not diagnosed with COVID-19 (PR 0.92 [0.68–1.24]). The prevalence was statistically significantly elevated among individuals diagnosed with COVID-19 for eight of the fifteen measured symptoms: shortness of breath, chest pain, dizziness, heart racing, headaches, low energy/fatigue, trouble sleeping, and back pain. The analysis of repeated measurements rendered similar results as the main analysis. Interpretation: These data suggest an elevated prevalence of some, but not all, physical symptoms during up to more than 2 years after diagnosis of COVID-19, particularly among individuals suffering a severe acute illness, highlighting the importance of continued monitoring and alleviation of these targeted core symptoms. Funding: This work was mainly supported by grants from NordForsk (COVIDMENT, grant number 105668 and 138929) and Horizon 2020 (CoMorMent, 847776). See Acknowledgements for further details on funding.