A two-step pathway consisting of an acyl-acyl carrier protein (ACP) reductase (AAR) and an aldehyde deformylating oxygenase (ADO) allows various cyanobacteria to convert long-chain fatty acids into hydrocarbons. AAR catalyzes the two-electron NADPH-dependent reduction of a fatty acid attached to ACP via a thioester linkage to the corresponding fatty aldehyde, while ADO transforms the fatty aldehyde to a Cn-1 hydrocarbon and C1-derived formate. Considering that heptadec(a/e)ne is the most prevalent hydrocarbon produced by cyanobacterial ADOs, the insolubility of its precursor, octadec(a/e)nal, poses a conundrum with respect to its acquisition by ADO. Herein, we report that AAR from the cyanobacterium Nostoc punctiforme is activated almost 20-fold by potassium and other monovalent cations of similar ionic radius, and that AAR and ADO form a tight isolable complex with a Kd of 3 ± 0.3 µM. In addition, we show that when the aldehyde substrate is supplied to ADO by AAR, efficient in vitro turnover is observed in the absence of solubilizing agents. Similarly to studies by Lin et al. with AAR from Synechococcus elongatus, we show that catalysis by AAR proceeds via formation of a covalent intermediate involving a cysteine residue that we have identified as Cys294. Moreover, AAR specifically transfers the pro-R hydride of NADPH to the Cys294-thioester intermediate to afford its aldehyde product. Our results suggest that the interaction between AAR and ADO facilitates either direct transfer of the aldehyde product of AAR to ADO or formation of the aldehyde product in a microenvironment allowing for its efficient uptake by ADO.