The putatively asexual Colpodean ciliates potentially pose a problem to macro-organismic theories of evolution. They are extremely ancient (although asexuality is thought to hasten extinction), and yet there is one apparently derived sexual species (implying an unlikely regain of a complex trait). If macro-organismic theories of evolution also broadly apply to microbial eukaryotes, though, then most or all of the colpodean ciliates should merely be secretively sexual. Here we show using de novo genome sequencing, that colpodean ciliates have the meiotic genes required for sex and these genes are under functional constraint. Along with these genomic data, we argue that these ciliates are sexual given the cytological observations of both micronuclei and macronuclei within their cells, and the behavioral observations of brief fusions as if the cells were mating. The challenge that colpodean ciliates pose is therefore not to evolutionary theory, but to our ability to induce microbial eukaryotic sex in the laboratory.