Prenyltransferases (PTs) catalyze the regioselective transfer of prenyl moieties onto aromatic substrates in biosynthetic pathways of microbial secondary metabolites. Therefore, these enzymes contribute to the chemical diversity of natural products. Prenylation is frequently essential for the pharmacological properties of these metabolites, including their antibiotic and antitumor activities. Recently, the first phenazine PTs, termed EpzP and PpzP, were isolated and biochemically characterized. The two enzymes play a central role in the biosynthesis of endophenazines by catalyzing the regiospecific prenylation of 5,10-dihydrophenazine-1-carboxylic acid (dhPCA) in the secondary metabolism of two different Streptomyces strains. Here we report crystal structures of EpzP in its unliganded state as well as bound to S-thiolodiphosphate (SPP), thus defining the first three-dimensional structures for any phenazine PT. A model of a ternary complex resulted from in silico modeling of dhPCA and site-directed mutagenesis. The structural analysis provides detailed insight into the likely mechanism of phenazine prenylation. The catalytic mechanism suggested by the structure identifies amino acids that are required for catalysis. Inspection of the structures and the model of the ternary complex furthermore allowed us to rationally engineer EpzP variants with up to 14-fold higher catalytic reaction rate compared to the wild-type enzyme. This study therefore provides a solid foundation for additional enzyme modifications that should result in efficient, tailor-made biocatalysts for phenazines production.