Very few animals habitually manufacture and use tools. It has been suggested that advanced tool behaviour co-evolves with a suite of behavioural, morphological and life history traits. In fact, there are indications for such an adaptive complex in tool-using crows (genus Corvus species). Here, we sequenced the genomes of two habitually tool-using and ten non-tool-using crow species to search for genomic signatures associated with a tool-using lifestyle. Using comparative genomic and population genetic approaches, we screened for signals of selection in protein-coding genes in the tool-using New Caledonian and Hawaiian crows. While we detected signals of recent selection in New Caledonian crows near genes associated with bill morphology, our data indicate that genetic changes in these two lineages are surprisingly subtle, with little evidence at present for convergence. We explore the biological explanations for these findings, such as the relative roles of gene regulation and protein-coding changes, as well as the possibility that statistical power to detect selection in recently diverged lineages may have been insufficient. Our study contributes to a growing body of literature aiming to decipher the genetic basis of recently evolved complex behaviour.