Despite a strong history of theoretical work on the mechanisms of social evolution, relatively little is known of the molecular genetic changes that accompany transitions from solitary to eusocial forms. Here we provide the first genome of an incipiently social bee that shows both solitary and social colony organization in sympatry, the Australian carpenter bee Ceratina australensis. Through comparative analysis, we provide support for the role of conserved genes and cis-regulation of gene expression in the phenotypic plasticity observed in nest-sharing, a rudimentary form of sociality. Additionally, we find that these conserved genes are associated with caste differences in advanced eusocial species, suggesting these types of mechanisms could pave the molecular pathway from solitary to eusocial living. Genes associated with social nesting in this species show signatures of being deeply conserved, in contrast to previous studies in other bees showing novel and faster-evolving genes are associated with derived sociality. Our data provide support for the idea that the earliest social transitions are driven by changes in gene regulation of deeply conserved genes.