The cytochrome P450 enzyme OleTJE from Jeotgalicoccus sp. ATCC 8456 is capable of converting free long-chain fatty acids into α-alkenes via one-step oxidative decarboxylation in presence of H2O2 as cofactor or using redox partner systems. This enzyme has attracted much attention due to its intriguing but unclear catalytic mechanism and potential application in biofuel production. Here, we investigated the functionality of a select group of residues (Arg245, Cys365, His85, and Ile170) in the active site of OleTJE through extensive mutagenesis analysis. The key roles of these residues for catalytic activity and reaction type selectivity were identified. In addition, a range of heterologous redox partners were found to be able to efficiently support the decarboxylation activity of OleTJE. The best combination turned out to be SeFdx-6 (ferredoxin) from Synechococcus elongatus PCC 7942 and CgFdR-2 (ferredoxin reductase) from Corynebacterium glutamicum ATCC 13032, which gave the highest myristic acid conversion rate of 94.4%. Moreover, Michaelis-Menton kinetic parameters of OleTJE towards myristic acid were determined.