Bacterial contamination during fuel storage can lead to fuel biodegradation (biodeterioration) or infrastructure problems (i.e., microbiologically influenced corrosion (MIC), biofouling, etc.). Jet A-1 storage tank samples were screened, and 23 morphologically distinct bacterial strains were isolated. 6 isolates revealed biofilm initiation capacity. For 12 isolates the alkane monooxygenase gene (alkB) was successfully detected. The 12 alkB-possessing isolates were 16S rDNA sequences identified as belonging to Bradyrhizobium, Sphingomonas, Bacillus, Pseudomonas, Methylobacterium and Lelliottia genera. In addition to possessing enzymatic equipment (AlkB) required for alkane oxidation, 10 out of 12 isolates were able to use Jet A-1 and n-tetradecane as their sole carbon source and energy. Biofilm initiation capacity and the ability to grow on different hydrocarbons highlights once again that fuel bacterial contamination can lead to serious fuel and storage system alterations. In contrast, their adaptation to high concentrations of hydrocarbons highlights the potential use of our isolates for bioremediation processes.