How new molecular functions emerge is a fundamental question in evolutionary biology. Here we focus on the homeodomain (HD) transcription factor Bicoid (Bcd), which emerged from a gene duplication that also gave rise to the paralogous protein Zen. After the duplication, Bcd diverged rapidly from Zen throughout its protein sequence, and acquired a pivotal role in anterior embryo patterning. We have used an in vivo rescue assay to test chimeric proteins that swap the HDs between Bcd and Zen. These experiments show that the Bcd HD is essential for anterior patterning, and that it can provide many of Bcd’s molecular functions when inserted into Zen. To understand how the Bcd HD gained novel functions during evolution, we took an ancestral protein resurrection approach. Using a maximum likelihood-based method, we predicted HD sequences of the ancestors of extant Zen and Bcd proteins. The “ancestral HD” of Zen and Bcd (AncZen-Bcd HD) prefers a consensus Zen DNA-binding motif (ZM), and chimeric Bcd proteins containing this HD sequences cannot replace any of the patterning functions missing in embryos lacking Bcd. Further conservation analysis identified eleven amino acids in the HD as critical for Bcd evolution. Only two of these amino acids significantly change the in vitro binding activities of the HD. Substitutions of one (K50) is sufficient to convert the in vitro DNA binding specificity of the AncZen-Bcd HD to that of present-day Bcd. In vivo analyses showed that this amino acid is also required for Bcd’s patterning functions. However, when introduced into the AncZen-Bcd HD, there is only a partial rescue of the bcd mutant, and activation of only a subset of Bcd target genes. We also tested R54, a second amino acid previously shown to be required for Bcd's RNA-binding activity. We find that insertion of R54 into the AncZen-Bcd HD does not change its in vitro DNA-binding specificity or activate Bcd target genes on its own. However, when both K50 and R54 are introduced into the AncZen-Bcd HD, its DNA-binding activity changes, and it turns on a larger subset of Bcd target genes compared to the K50 substitution alone. Our results show an interdependence between K50 and R54 in DNA-binding activity, and suggest that the evolution of Bcd involved step-by-step single amino acid substitutions that enabled the evolving protein to activate different subsets of target genes.