Heterogeneity in eukaryotic and bacteria community structure in surface and subsurface sediment samples downgradient of the Banisveld landfill (The Netherlands) was studied using a culturing-independent molecular approach. Along a transect covering the part of the aquifer most polluted by landfill leachate, sediment was sampled at 1-m depth intervals, until a depth of 5.5 m, at four distances from the landfill. Two drillings were placed in a nearby clean area as a reference. Denaturing gradient gel electrophoresis banding patterns revealed high bacterial and eukaryotic diversity and complex community structures. Bacteria and eukaryotic community profiles in polluted samples grouped different from those in clean samples. Bacteria community profiles in surface samples clustered together and separately from subsurface community profiles. Subsurface bacteria profiles clustered in a location-specific manner. Eukaryotic community structure did not significantly relate to distance from the landfill or depth. No significant spatial autocorrelation of bacteria or eukaryotic communities was observed over 1-m depth intervals per sampling location. Spatial heterogeneity in sediment-associated bacterial communities appears to be much larger than in groundwater. We discuss how on the one hand, spatial heterogeneity may complicate the assessment of microbial community structure and functioning, while on the other it may provide better opportunities for natural attenuation. © 2008 Federation of European Microbiological Societies. Published by Blackwell Publishing Ltd. All rights reserved.