Background: Aldehyde decarbonylase (AD), which converts acyl aldehydes into alkanes, supplies promising solution for producing alkanes from renewable feedstock. However the instability of AD impeded its further application. Therefore, the current study aimed to investigate the degradation mechanism of AD and engineer it towards high stability. Results: Here, we describe the discovery of a degradation tag (degron) in the AD from marine cyanobacterium Prochlorococcus marinus via error-prone PCR based directed evolution system. Bioinformatic analysis revealed this C-terminal degron is common in the family of bacterial ADs and identified a conserved C-terminal motif, RMSAYGLAAA, representing the AD degron (ADcon). Furthermore, we demonstrated that the ATP-dependent proteases ClpAP and Lon are involved in the degradation of AD-tagged proteins in E. coli , thereby limiting alkane production. Deletion or modification of the degron motif increased alkane production in vivo . Conclusions: This work revealed the presence of a novel degron in bacterial ADs responsible for its instability. The in vivo experiments proved eliminating or modifying the degron could stabilize AD, thereby producing higher titers of alkanes.