Two bacterial strains, i.e. Pseudomonas mendocina and Ochrobactrum sp. were isolated from bilge oil contaminated water of Mormugao harbour, Goa, India and grown in a culture medium with hexadecane as the sole carbon source. Pseudomonas mendocina was used in further studies as it was the dominant strain. This strain effectively degraded tetradecane, hexadecane and octadecane leaving a residual concentration of about 73 %, 54 % and 40 % respectively in 120 h. Sequence analysis of the dominant bands from the denaturing gradient gel electrophoresis profiles revealed the differences between the genera of bilge oil contaminated sea water and its enrichment culture on hexadecane indicating a shift in community structure based on the type of substrate available. Pseudomonas mendocina amplified for the following catabolic genes namely C230, nid and ndo. Based on the catabolic gene study the potential of the bacterial strain isolated, i.e. Pseudomonas mendocina seems to be interesting as it will be able to degrade polyaromatic hydrocarbons as well. Physicochemical properties of Pseudomonas mendocina indicates production of exopolysaccharides based on the value of its isoelectric point.