Metagenomics has been successfully applied to isolate novel biocatalysts from diverse environments and functional screening has been used as the primary technique to identify clones carrying the desired traits. This work aimed at the construction and screening of a metagenomic library as a source of potential hydrocarbon biodegraders. A library of 31000 clones was obtained from aerobic and anaerobic enrichments generated using a biodegraded petroleum sample collected at the Potiguar Basin in Brazil as an inoculum. A total of 5000 clones were randomly selected for high throughput screening of hexadecane biodegradation, revealing 72 positive hits. These were further evaluated using gas chromatography–mass spectrometry (GC–MS), outstanding hexadecane biodegradation ability (>70%) being detected in five clones.