Very-long-chain polyunsaturated fatty acids, such as arachidonic acid (ARA), eicosapentaenoic acid (EPA), and docosahexaenoic acid (DHA), have well-documented importance in human health and nutrition. Sustainable production in robust host organisms that do not synthesize them naturally requires the coordinated expression of several heterologous desaturases and elongases. In the present study we show production of EPA in Saccharomyces cerevisiae using glucose as the sole carbon source through expression of five heterologous fatty acid desaturases and an elongase. Novel Δ5-desaturases from the ciliate protozoan Paramecium tetraurelia and from the microalgae Ostreococcus tauri and Ostreococcus lucimarinus were identified via a BLAST search, and their substrate preferences and desaturation efficiencies were assayed in a yeast strain producing the ω6 and ω3 fatty acid substrates for Δ5-desaturation. The Δ5-desaturase from P. tetraurelia was up-to-2-fold more efficient than the microalgal desaturases and was also more efficient than Δ5-desaturases from Mortierella alpina and Leishmania major. In vivo investigation of acyl carrier substrate specificities showed that the Δ5-desaturases from P. tetraurelia, O. lucimarinus, O. tauri, and M. alpina are promiscuous toward the acyl carrier substrate but prefer phospholipid-bound substrates. In contrast, the Δ5-desaturase from L. major showed no activity on phospholipid-bound substrate and thus appears to be an exclusively acyl coenzyme A-dependent desaturase.