Gene regulatory networks are the programs that translate genomic information into body plans and structures during development. Regulatory genes that compose such networks are often highly multifunctional and constrained, which results in evolutionary conservation. It is difficult to understand how a regulatory gene could be lost from the genome of one species when it is essential for viability in closely related species. The segmentation gene paired is a classic Drosophila pair-rule gene, required for formation of alternate body segments. paired is highly conserved; it is required for pair-rule patterning in distantly-diverged insects from flies to beetles. Surprisingly, paired was lost in mosquitos without morphological consequence on body patterning. Here, we demonstrate that a paired family member, gooseberry, has acquired paired-like expression in Anopheles stephensi, the Asian malaria mosquito. Using CRISPR-Cas9, we generated a targeted knock-out of Anopheles-gooseberry and found that mutants display pair-rule phenotypes similar to those seen for Drosophila-paired. Further, this loss-of-function mutation in gooseberry resulted in the same alteration of downstream target gene expression observed in Drosophila and beetle paired mutants. Thus, paired was functionally replaced by the related gene, gooseberry, in mosquito lineages. Our findings document a rare example of a functional replacement of an essential regulatory gene and provide a mechanistic explanation of how the loss of regulatory genes can occur during evolution.