Hydrocarbon seeps provide inputs of petroleum hydrocarbons to widespread areas of the Timor Sea. Alkanes constitute the largest proportion of chemical components found in crude oils, and therefore genes involved in the biodegradation of these compounds may act as bioindicators for this ecosystem's response to seepage. To assess alkane biodegradation potential, the diversity and distribution of alkane hydroxylase (alkB) genes in sediments of the Timor Sea were studied. Deduced AlkB protein sequences derived from clone libraries identified sequences only distantly related to previously identified AlkB sequences, suggesting that the Timor Sea maybe a rich reservoir for novel alkane hydroxylase enzymes. Most sequences clustered with AlkB sequences previously identified from marine Gammaproteobacteria though protein sequence identities averaged only 73% (with a range of 60% to 94% sequence identities). AlkB sequence diversity was lower in deep water (>400 m) samples off the continental slope than in shallow water (<100 m) samples on the continental shelf but not significantly different in response to levels of alkanes. Real-time PCR assays targeting Timor Sea alkB genes were designed and used to quantify alkB gene targets. No correlation was found between gene copy numbers and levels of hydrocarbons measured in sediments using sensitive gas chromatography-mass spectrometry techniques, probably due to the very low levels of hydrocarbons found in most sediment samples. Interestingly, however, copy numbers of alkB genes increased substantially in sediments exposed directly to active seepage even though only low or undetectable concentrations of hydrocarbons were measured in these sediments in complementary geochemical analyses due to efficient biodegradation.