Learning reflects the influence of experience on genetically determined circuitry. Both the ways in which experience shapes behavior during learning and the ways in which genetics shape non-learned phenotypes have been widely studied. However, little is known about how experience and genetics interact to determine complex learned phenotypes. Vocal learning in songbirds provides a rich system for investigating experiential and genetic contributions to learning; the output of learning (song) is quantifiable and we can manipulate both the experiential contributions (through computer tutoring) and genetic contributions (through breeding). Here we examine the relationship between experiential and genetic contributions to learning of an ethologically relevant phenotype, the tempo of song production (quantified in syllables produced per second). Distinct genetic lines of the Bengalese finch (Lonchura striata domesitca) were bred from parents with different song tempos. When juvenile birds of a given line were tutored with synthetic songs that varied only in tempo, they developed adult songs with tempos that varied with the tutor song. Hence, as expected, the structure of song was shaped by experience. However, when the tempo of the tutor song was held constant, juveniles from different genetic lines developed song tempos that strongly correlated with those of their fathers, even though these juveniles had never heard their fathers sing. Thus, under controlled tutoring conditions, we found an unexpectedly strong genetic contribution to the mean song tempo. We further investigated the interaction between genetics and experience by tutoring several genetic lines (that expressed slow, medium and fast songs) on a set of synthetic songs that differed only in tempo. We again found that, across all lines, tutoring experience influenced song tempo. However, each line learned different amounts of the stimulus tempo, revealing a significant gene by environment interaction (GXE; a non-linear interaction between genetic and experiential contributions to song tempo). Taken together, these findings demonstrate a strong genetic contribution both to the mean tempo of song and to the degree to which tempo is influenced by experience. Our results provide a striking demonstration of how genetics can both shape and constrain the influence of experience on a complex learned phenotype.