Aims Due to the significant value held by medical records in terms of influencing patient care and medico-legal cases, this study aimed to investigate the quality of surgical notes and their improvement through periodic auditing during a six-year period at a major tertiary hospital. Methodology This study retrospectively evaluated surgical records of patients undergoing elective orthopedic surgeries at Jordan University Hospital from 2016 to 2021 using the Surgical Tool for Auditing Records (STAR) validated questionnaire. This questionnaire is composed of six distinct sections aimed to quantify the quality of medical records and demonstrate their associated deficiencies. Pre- and post-audit STAR scores were analyzed using the two independent sample t-test on Statistical Package for Social Sciences (SPSS) version 23.0 (IBM Corp. Armonk, NY). Results A total of 454 records were randomly selected and evaluated using the STAR questionnaire. There was an overall significant trend of improvement in the quality of records in all evaluated years compared to the 2016 baseline. The most pronounced improvements were in the records of 2021 as compared to the 2016 baseline (97.4 ± 0.7 vs. 94.3 ± 1.6; p:<0.05), in which the Initial Clerking, Subsequent Entries, and Operative Record domains had the most significant magnitude of change. The Consent and Anesthesia domains plateaued over the study's period in terms of overall quality. The most improved STAR domain was the Discharge Summary domain, in which four subsections (follow-up, diagnosis, complications, and medications on discharge) had significant STAR score increases (all; p:<0.05). Conclusion Our study implies that simple measures, including personnel education and training and periodic auditing, are effective measures in increasing the quality of surgical records. High-quality medical records need to be sustained and continuously improved, as they contribute to better health care, promote research, and contribute to economic gains through cost-effective practices.