The acquisition of the external genitalia allowed mammals to cope with terrestrial-specific reproductive needs for internal fertilization, and thus it represents one of the most fundamental steps in evolution towards a life on land. How genitalia evolved remains obscure, and the key to understanding this process may lie in the developmental genetics that underpins the early establishment of the genital primordium, the genital tubercle (GT). Development of the GT is similar to that of the limb, which requires precise regulation from a distal signaling epithelium. However, whether outgrowth of the GT and limbs is mediated by common instructive signals remains unknown. In this study, we used comprehensive genetic approaches to interrogate the signaling cascade involved in GT formation in comparison with limb formation. We demonstrate that the FGF ligand responsible for GT development is FGF8 expressed in the cloacal endoderm. We further showed that forced Fgf8 expression can rescue limb and GT reduction in embryos deficient in WNT signaling activity. Our studies show that the regulation of Fgf8 by the canonical WNT signaling pathway is mediated in part by the transcription factor SP8. Sp8 mutants elicit appendage defects mirroring WNT and FGF mutants, and abolishing Sp8 attenuates ectopic appendage development caused by a gain-of-function β-catenin mutation. These observations indicate that a conserved WNT-SP8-FGF8 genetic cassette is employed by both appendages for promoting outgrowth, and suggest a deep homology shared by the limb and external genitalia.