We performed a genome-wide association study of total hip replacements, based on variants identified through whole-genome sequencing, which included 4,657 Icelandic patients and 207,514 population controls. We discovered two rare signals that strongly associate with osteoarthritis total hip replacement: a missense variant, c.1141G>C (p.Asp369His), in the COMP gene (allelic frequency = 0.026%, P = 4.0 × 10-12, odds ratio (OR) = 16.7) and a frameshift mutation, rs532464664 (p.Val330Glyfs*106), in the CHADL gene that associates through a recessive mode of inheritance (homozygote frequency = 0.15%, P = 4.5 × 10-18, OR = 7.71). On average, c.1141G>C heterozygotes and individuals homozygous for rs532464664 had their hip replacement operation 13.5 years and 4.9 years earlier than others (P = 0.0020 and P = 0.0026), respectively. We show that the full-length CHADL transcript is expressed in cartilage. Furthermore, the premature stop codon introduced by the CHADL frameshift mutation results in nonsense-mediated decay of the mutant transcripts.