Within the salamander family Plethodontidae, five different clades have evolved high levels of enucleated red blood cells, which are extremely unusual among non-mammalian vertebrates. In each of these five clades, the salamanders have large genomes and miniaturized or attenuated body forms. Such a correlation suggests that the loss of nuclei in red blood cells may be related, in part, to the interaction between large genome size and small body size, which has been shown to have profound morphological consequences for the nervous and visual systems in plethodontids. Previous work has demonstrated that variation in both the level of enucleated cells and the size of the nuclear genome exists among species of the monophyletic plethodontid genus Batrachoseps. Here, we report extensive intraspecific variation in levels of enucleated red blood cells in 15 species and provide measurements of red blood cell size, nucleus size, and genome size for 13 species of Batrachoseps. We present a new phylogenetic hypothesis for the genus based on 6150bp of mitochondrial DNA sequence data from nine exemplar taxa and use it to examine the relationship between genome size and enucleated red blood cell morphology in a phylogenetic framework. Our analyses demonstrate positive direct correlations between genome size, nucleus size, and both nucleated and enucleated cell sizes within Batrachoseps, although only the relationship between genome size and nucleus size is significant when phylogenetically independent contrasts are used. In light of our results and broader studies of comparative hematology, we propose that high levels of enucleated, variably sized red blood cells in Batrachoseps may have evolved in response to rheological problems associated with the circulation of large red blood cells containing large, bulky nuclei in an attenuate organism.