Male signals that advertise dominance are often also attractive to females, but female signals advertising dominance can make them less attractive to males. For example, in species where males are larger than females, low-frequency male vocalisations are expected to be selected by intra-sexual selection, inter-sexual selection and selection to identify sex, but these selective forces may act antagonistically on female vocalisations. Consistent with this, low-pitch human voices can be perceived as more dominant in both sexes and more attractive to the opposite sex in males, but less attractive to the opposite sex in females. Research on factors influencing the frequency of animal vocalisations has largely focused on males, and little is known about the drivers of variation in vocal pitch between sexes in animals. We tested for sex differences in a species where both sexes sing, the Australian magpie-lark (Grallina cyanleuca), by simulating a territorial intruder with experimentally manipulated high- or low-pitched playback songs. Both sexes sang significantly sooner and alarm called more in response to low-frequency playback, regardless of the sex of the ‘intruder’, suggesting that both sexes perceived low-frequency songs as more threatening. However, there were sex differences in how males and females changed their song frequencies in response to playback. Males sang at a lower frequency to low-pitched male than female playback. In contrast, females sang songs with a significantly higher frequency in response to low- than high-pitched male playback. Our results highlight that selection may act differently on song frequency in male and female birds.