Two new species of heterolobosean amoebae from anoxic environments, Monopylocystis visvesvarai and Sawyeria marylandensis, are described on the basis of light microscopy, electron microscopy, and their phylogenetic affiliation based on analyses of nuclear small-subunit ribosomal RNA gene sequences. Both species lack mitochondria but have organelles provisionally interpreted as hydrogenosomes, and neither can tolerate aerobic conditions. As their conditions of culture do not exclude all oxygen, they may be microaerophiles rather than strict anaerobes. Both species have unusual nucleolar morphologies. Monopylocystis visvesvarai, from a marine sediment, has nucleolar material distributed around the nuclear periphery. It is the first non-aerobic heterolobosean protist for which a cyst is known; the cyst is unmineralized and unornamented except for a single, raised, plugged pore. Sawyeria marylandensis, from an iron-rich freshwater stream, has nucleolar material distributed in one or two parietal masses, which persist during mitosis. In phylogenetic analyses of small-subunit rRNA gene sequences, Monopylocystis visvesvarai, Sawyeria marylandensis and Psalteriomonas lanterna converge to form a single clade of non-aerobic (anaerobic/microaerophilic) heteroloboseans.