The X-linked orange (O) locus in domestic cats controls an unknown molecular mechanism that causes the suppression of black-brownish pigmentation in favor of orange coloration. The alternating black-brownish and orange patches seen in tortoiseshell and calico cats are considered classic examples of the phenotypic expression of random X chromosome inactivation (XCI) occurring in female mammals. However, the O gene in the cat genome has not been identified, and the genetic variation responsible for the orange coloration remains unknown. We report here that a 5.1-kilobase (kb) deletion within an intron of the X-linked ARHGAP36 gene, encoding a Rho GTPase-activating protein, is closely and exclusively associated with orange coloration. The deleted region contains a highly conserved putative regulatory element, whose removal is presumed to alter ARHGAP36 expression. Notably, ARHGAP36 expression in cat skin tissues is linked to the suppression of many melanogenesis genes, potentially shifting pigment synthesis from eumelanin to pheomelanin. Furthermore, we find evidence that the gene undergoes XCI in female human and mouse cells and XCI-dependent CpG island methylation consistent with random XCI in female domestic cats. The 5.1-kb deletion seems widespread in domestic cats with orange coat coloration, suggesting a single origin of this coat color phenotype.