Hindlimb loss has evolved repeatedly in many different animals by means of molecular mechanisms that are still unknown. To determine the number and type of genetic changes underlying pelvic reduction in natural populations, we carried out genetic crosses between threespine stickleback fish with complete or missing pelvic structures. Genome-wide linkage mapping shows that pelvic reduction is controlled by one major and four minor chromosome regions. Pitx1 maps to the major chromosome region controlling most of the variation in pelvic size. Pelvic-reduced fish show the same left-right asymmetry seen in Pitx1 knockout mice, but do not show changes in Pitx1 protein sequence. Instead, pelvic-reduced sticklebacks show site-specific regulatory changes in Pitx1 expression, with reduced or absent expression in pelvic and caudal fin precursors. Regulatory mutations in major developmental control genes may provide a mechanism for generating rapid skeletal changes in natural populations, while preserving the essential roles of these genes in other processes.