Eigen’s Paradox is a logical puzzle concerned with the origin of complex life.  It is presumed that, early in the history of life, mutation rates were much higher than they are in contemporary organisms.  According to Manfred Eigen, this implies that the maximum amount of information that could have been stably encoded in the genomes of early organisms must have been severely limited. In contemporary organisms, the mechanisms of error prevention and correction are quite complex.  This leads to a “chicken-and-egg problem.”  How could life that is complex enough to allow the suppression of mutation to low levels have evolved while mutation rates were quite high?  Eigen’s calculations are based on the idea that, if the genome with the best-possible fitness can not be maintained in a population, then “The information ... would slowly seep away until it is entirely lost.”  However, this idea is not obviously based on any firm information theoretic foundation.  What really matters is whether, in a stable population, organisms are able to generate phenotypes that are complex enough to allow for highly effective error prevention and correction mechanisms.  Here, we re-analyze the problem using this phenotypic-complexity criterion.  We find that there are conditions where much more information can bestably encoded in the genome than would follow from Eigen’s criterion, despite the existence of relatively high mutation rates.  We find that the highest levels of information content are obtained when recombination occurs, and when each possible phenotype is produced by many different genotypes.