Terminal olefins (1-alkenes) are natural products that have important industrial applications as both fuels and chemicals. However, their biosynthesis has been largely unexplored. We describe a group of bacteria, Jeotgalicoccus spp., which synthesize terminal olefins, in particular 18-methyl-1-nonadecene and 17-methyl-1-nonadecene. These olefins are derived from intermediates of fatty acid biosynthesis, and the key enzyme in Jeotgalicoccus sp. ATCC 8456 is a terminal olefin-forming fatty acid decarboxylase. This enzyme, Jeotgalicoccus sp. OleT (OleT(JE)), was identified by purification from cell lysates, and its encoding gene was identified from a draft genome sequence of Jeotgalicoccus sp. ATCC 8456 using reverse genetics. Heterologous expression of the identified gene conferred olefin biosynthesis to Escherichia coli. OleT(JE) is a P450 from the cyp152 family, which includes bacterial fatty acid hydroxylases. Some cyp152 P450 enzymes have the ability to decarboxylate and to hydroxylate fatty acids (in α- and/or β-position), suggesting a common reaction intermediate in their catalytic mechanism and specific structural determinants that favor one reaction over the other. The discovery of these terminal olefin-forming P450 enzymes represents a third biosynthetic pathway (in addition to alkane and long-chain olefin biosynthesis) to convert fatty acid intermediates into hydrocarbons. Olefin-forming fatty acid decarboxylation is a novel reaction that can now be added to the catalytic repertoire of the versatile cytochrome P450 enzyme family.