While chemical communication regulates individual behavior in a wide variety of species, these communication systems are most elaborated in insect societies. In these complex systems, pheromones produced by the reproductive individuals (queens) are critical in establishing and maintaining dominant reproductive status over hundreds to thousands of workers. The proximate and ultimate mechanisms by which these intricate pheromone communication systems evolved are largely unknown, though there has been much debate over whether queen pheromones function as a control mechanism or as an honest signal facilitating cooperation. Here, we summarize results from recent studies in honey bees, bumble bees, wasps, ants and termites. We further discuss evolutionary mechanisms by which queen pheromone communication systems may have evolved. Overall, these studies suggest that queen-worker pheromone communication is a multi-component, labile dialog between the castes, rather than a simple, fixed signal-response system. We also discuss future approaches that can shed light on the proximate and ultimate mechanisms that underlie these complex systems by focusing on the development of increasingly sophisticated genomic tools and their potential applications to examine the molecular mechanisms that regulate pheromone production and perception.