Samples of surface bottom sediments were taken at 82 stations in Lithuania’s Klaipeda harbour in 2008- 09. Sediment parameters such as the percentages of particles and the concentrations of organic carbon and heavy metals (Cu, Zn, Ni, Pb, Cr, Cd, and Hg) were determined. The heavy metal contamination of harbor sediments was established by calculating Nemerov’s pollution index applied to soil. The spatial structure of the obtained data and the factors responsible for sediment distribution and contamination patterns were analyzed in order to evaluate the changes that have occurred since 1998 in the sedimentation conditions, the level of heavy metal contamination, and the structure of the contaminants.