Abstract Background Long-term sequelae of COVID-19 can result in reduced functionality of the central nervous system and substandard quality of life. Gaining insight into the recovery trajectory of admitted COVID-19 patients on their cognitive performance and global structural brain connectivity may allow a better understanding of the diseases' relevance. Objectives To assess whole-brain structural connectivity in former non-intensive-care unit (ICU)- and ICU-admitted COVID-19 survivors over 2 months following hospital discharge and correlate structural connectivity measures to cognitive performance. Methods Participants underwent Magnetic Resonance Imaging brain scans and a cognitive test battery after hospital discharge to evaluate structural connectivity and cognitive performance. Multilevel models were constructed for each graph measure and cognitive test, assessing the groups' influence, time since discharge, and interactions. Linear regression models estimated whether the graph measurements affected cognitive measures and whether they differed between ICU and non-ICU patients. Results Six former ICU and six non-ICU patients completed the study. Across the various graph measures, the characteristic path length decreased over time (β = 0.97, p = 0.006). We detected no group-level effects (β = 1.07, p = 0.442) nor interaction effects (β = 1.02, p = 0.220). Cognitive performance improved for both non-ICU and ICU COVID-19 survivors on four out of seven cognitive tests 2 months later (p < 0.05). Conclusion Adverse effects of COVID-19 on brain functioning and structure abate over time. These results should be supported by future research including larger sample sizes, matched control groups of healthy non-infected individuals, and more extended follow-up periods.