Two commonly used procedures for early stage hallux rigidus are cheilectomy and decompression metatarsal osteotomy. However, although both procedures were first described several decades ago, a deficit exists in the published data comparing their effectiveness. We performed a retrospective comparative study to examine the results of surgical treatment of early-stage hallux rigidus. A total of 423 subjects were included. Hallux limitus or rigidus had been diagnosed in all patients, who had undergone either cheilectomy or any variation of plantarflexion decompression metatarsal head osteotomy. Of the 423 procedures identified during the study period, 341 (80.6%) were cheilectomy and 82 (19.4%) were decompression osteotomy procedures. The rate of revision procedures was significantly greater in the cheilectomy group (8.21%) than in the osteotomy group (1.22%). Sex, laterality, and body mass index played no role in the rate of revision. The absence of research studies comparing the effectiveness of the 2 procedures has led many practitioners to favor cheilectomy for early-stage hallux rigidus. Decompression metatarsal osteotomies are technically more difficult, involve more risks, and require greater restrictions on postoperative weightbearing compared with cheilectomy. However, our data have shown that within the first 5 postoperative years, decompression osteotomy resulted in a dramatically lower rate of revisional surgery for first metatarsophalangeal joint pathology compared with cheilectomy.