Treatment outcomes in implant dentistry have been mainly assessed as implant survival rates in small, selected patient groups of specialist or university clinical settings. This study reports on loss of dental implants assessed in a large and randomly selected patient sample. The results were aimed at representing evaluation of effectiveness of implant dentistry. Using the national data register of the Swedish Social Insurance Agency, 4,716 patients were randomly selected. All had been provided with implant-supported restorative therapy in 2003. Patient files of 2,765 patients (11,311 implants) were collected from more than 800 clinicians. Information on patients, treatment procedures, and outcomes related to the implant-supported restorative therapy was extracted from the files. In total, 596 of the 2,765 subjects, provided with 2,367 implants, attended a clinical examination 9 y after therapy. Implant loss that occurred prior to connection of the supraconstruction was scored as an early implant loss, while later occurring loss was considered late implant loss. Early implant loss occurred in 4.4% of patients (1.4% of implants), while 4.2% of the patients who were examined 9 y after therapy presented with late implant loss (2.0% of implants). Overall, 7.6% of the patients had lost at least 1 implant. Multilevel analysis revealed higher odds ratios for early implant loss among smokers and patients with an initial diagnosis of periodontitis. Implants shorter than 10 mm and representing certain brands also showed higher odds ratios for early implant loss. Implant brand also influenced late implant loss. Implant loss is not an uncommon event, and patient and implant characteristics influence outcomes (ClinicalTrials.gov NCT01825772).