Thelytokous parthenogenesis, or the asexual production of female offspring, is rare in the animal kingdom, but relatively common in social Hymenoptera. However, in honeybees, it is only known to be ubiquitous in one subspecies of Apis mellifera, the Cape honeybee, A. mellifera capensis. Here we report the appearance of queen cells in two colonies of the Eastern honeybee Apis cerana that no longer contained a queen or queen-produced brood to rear queens from. A combination of microsatellite genotyping and the timing of the appearance of these individuals excluded the possibility that they had been laid by the original queen. Based on the genotypes of these individuals, thelytokous production by natal workers is the most parsimonious explanation for their existence. Thus, we present the first example of thelytoky in a honeybee outside A. mellifera. We discuss the evolutionary and ecological consequences of thelytoky in A. cerana, in particular the role thelytoky may play in the recent invasions by populations of this species.