Pollution of petroleum hydrocarbons, in particular oil spills, has attracted much attention in the past and recent decades. Oil spills influence natural microbial community, and physical and chemical properties of the affected sites. The biodegradation of hydrocarbons by microorganisms is one of the primary ways by which oil spill is eliminated from contaminated sites. One such spill was that of the Russian tanker the Nakhodka that spilled heavy oil into the Sea of Japan on January 2, 1997. The impact of the Nakhodka oil spill resulted in a viscous sticky fluid fouling the shores and affected natural ecosystems. This paper describes the weathering of hydrocarbon-degrading bacteria (genus Pseudomonas) and crystallized organic compounds from the Nakhodka oil spill-polluted seashores after nine years. The Nakhodka oil has hardened and formed crust of crystalline paraffin wax as shown by XRD analysis (0.422, 0.377, and 0.250 nm d-spacing) in association with graphite and calcite after 9 years of bioremediation. Anaerobic reverse side of the oil crust contained numerous coccus typed bacteria associated with halite. The finding of hydrocarbon-degrading bacteria and paraffin wax in the oil crust may have a significant effect on the weathering processes of the Nakhodka oil spill during the 9-year bioremediation.