Small hemoproteins displaying amino acid sequences 20-40 residues shorter than (non-)vertebrate hemoglobins (Hbs) have recently been identified in several pathogenic and non-pathogenic unicellular organisms, and named 'truncated hemoglobins' (trHbs). They have been proposed to be involved not only in oxygen transport but also in other biological functions, such as protection against reactive nitrogen species, photosynthesis or to act as terminal oxidases. Crystal structures of trHbs from the ciliated protozoan Paramecium caudatum and the green unicellular alga Chlamydomonas eugametos show that the tertiary structure of both proteins is based on a 'two-over-two' alpha-helical sandwich, reflecting an unprecedented editing of the classical 'three-over-three' alpha-helical globin fold. Based on specific Gly-Gly motifs the tertiary structure accommodates the deletion of the N-terminal A-helix and replacement of the crucial heme-binding F-helix with an extended polypeptide loop. Additionally, concerted structural modifications allow burying of the heme group and define the distal site, which hosts a TyrB10, GlnE7 residue pair. A set of structural and amino acid sequence consensus rules for stabilizing the fold and the bound heme in the trHbs homology subfamily is deduced.