Prolyl 4-hydroxylases (P4Hs) are 2-oxoglutarate dioxygenases that catalyze the hydroxylation of peptidyl prolines. They play an important role in collagen synthesis, oxygen homeostasis, and plant cell wall formation. We describe four structures of a P4H from the green alga Chlamydomonas reinhardtii, two of the apoenzyme at 1.93 and 2.90 A resolution, one complexed with the competitive inhibitor Zn2+, and one with Zn2+ and pyridine 2,4-dicarboxylate (which is an analogue of 2-oxoglutarate) at 1.85 A resolution. The structures reveal the double-stranded beta-helix core fold (jellyroll motif), typical for 2-oxoglutarate dioxygenases. The catalytic site is at the center of an extended shallow groove lined by two flexible loops. Mutagenesis studies together with the crystallographic data indicate that this groove participates in the binding of the proline-rich peptide-substrates. It is discussed that the algal P4H and the catalytic domain of collagen P4Hs have notable structural similarities, suggesting that these enzymes form a separate structural subgroup of P4Hs different from the hypoxia-inducible factor P4Hs. Key structural differences between these two subgroups are described. These studies provide first insight into the structure-function relationships of the collagen P4Hs, which unlike the hypoxia-inducible factor P4Hs use proline-rich peptides as their substrates.