Nucleosomes can be covalently modified by addition of various chemical groups on several of their exposed histone amino acids. These modifications are added and removed by enzymes (writers) and can be recognized by nucleosome-binding proteins (readers). Linking a reader domain and a writer domain that recognize and create the same modification state should allow nucleosomes in a particular modification state to recruit enzymes that create that modification state on nearby nucleosomes. This positive feedback has the potential to provide the alternative stable and heritable states required for epigenetic memory. However, analysis of simple histone codes involving interconversions between only two or three types of modified nucleosomes has revealed only a few circuit designs that allow heritable bistability. Here we show by computer simulations that a histone code involving alternative modifications at two histone positions, producing four modification states, combined with reader-writer proteins able to distinguish these states, allows for hundreds of different circuits capable of heritable bistability. These expanded possibilities result from multiple ways of generating two-step cooperativity in the positive feedback--through alternative pathways and an additional, novel cooperativity motif. Our analysis reveals other properties of such epigenetic circuits. They are most robust when the dominant nucleosome types are different at both modification positions and are not the type inserted after DNA replication. The dominant nucleosome types often recruit enzymes that create their own type or destroy the opposing type, but never catalyze their own destruction. The circuits appear to be evolutionary accessible, most circuits can be changed stepwise into almost any other circuit without losing heritable bistability. Thus, our analysis indicates that systems that utilize an expanded histone code have huge potential for generating stable and heritable nucleosome modification states and identifies the critical features of such systems.