In social insects, individuals typically recognize and behave aggressively towards alien conspecifics, thereby maintaining colony integrity. This is presumably achieved via a nestmate recognition system in which cuticular compounds, usually cuticular hydrocarbons (CHC), of genetic and/or environmental origin serve as recognition cues. Most invasive populations of the Argentine ant, Linepithema humile (Mayr), display minimal nestmate-non-nestmate discrimination, resulting in low levels of intraspecific aggression allowing free movement of workers and queens among nests. However, invasive L. humile in the southeastern United States show relatively high levels of intraspecific aggression, and selectively adopt non-nestmate queens. Using behavioral assays and gas chromatography, we found an association between non-nestmate queen adoption and similarity of the CHC profiles of adopted and host colony queens. Also, nestmate and non-nestmate queen CHC profiles became more similar after adoption by queenless colonies. Furthermore, queens treated with non-nestmate queen CHC had distinct CHC profiles and were generally attacked by nestmate workers. We suggest that in L. humile, CHC are used as queen recognition cues, and that queen recognition errors are more likely to occur when the CHC profiles of non-nestmate and host colony queens are similar. Our findings provide further evidence for the complex and dynamic nature of L. humile nestmate discrimination, which may in part underlie the success of introduced populations of this invasive ant.