Summary The objective of this paper was to study whether the bioremediation potential of coastal materials for oil-polluted sea water depended on the numbers of hydrocarbon-utilizing bacteria they naturally harbor. Inshore water of the Arabian Gulf was found to contain only about one thousand hydrocarbon-utilizing bacteria per ml. Coastal sand, cyanobacterial mats and epilithic biomass were much richer in these bacteria, with numbers ranging between several thousand fold to several million fold than in the water body. The predominant bacterium in all samples was Acinetobacter calcoaceticus, next in predominance were nocardioforms and Micrococcus sp. Inoculation, in batch cultures, of oily sea water or sea water containing pure hydrocarbons with fresh sea water, coastal sand, cyanobacterial mats or epilithic biomass harboring significantly different numbers of hydrocarbon-utilizing bacteria brought bioremediation effects that depended on fertilizing with KNO 3. In the absence of KNO 3, the bioremediation effect increased with numbers of hydrocarbon-utilizing bacteria in the inoculum. In the presence of KNO 3 similar bioremediation effects were found irrespective of the inoculated materials. The reason may be that bacteria reproduce quickly in closed cultures provided with nitrogen, reaching equal maximum numbers, irrespective of the inoculum size. This information could be useful in constructing technologies for oily sea water bioremediation.