The export of nitrogen from urban catchments is a global problem, and denitrifying bacteria in stream ecosystems are critical for reducing in-stream N. However, the environmental factors that control the composition of denitrifying communities in streams are not well understood. We determined whether denitrifying community composition in sediments of nine streams on the eastern fringe of Melbourne, Australia was correlated with two measures of catchment urban impact: effective imperviousness (EI, the proportion of a catchment covered by impervious surfaces with direct connection to streams) or septic tank density (which affects stream water chemistry, particularly stream N concentrations). Denitrifying community structure was examined by comparing terminal restriction fragment length polymorphisms of nosZ genes in the sediments, as the nosZ gene codes for nitrous oxide reductase, the last step in the denitrification pathway. We also determined the chemical and physical characteristics of the streams that were best correlated with denitrifying community composition. EI was strongly correlated with community composition and sediment physical and chemical properties, while septic tank density was not. Sites with high EI were sandier, with less fine sediment and lower organic carbon content, higher sediment cations (calcium, sodium and magnesium) and water filterable reactive phosphorus concentrations. These were also the best small-scale environmental variables that explained denitrifying community composition. Among our study streams, which differed in the degree of urban stormwater impact, sediment grain size and carbon content are the most likely drivers of change in community composition. Denitrifying community composition is another in a long list of ecological indicators that suggest the profound degradation of streams is caused by urban stormwater runoff. While the relationships between denitrifying community composition and denitrification rates are yet to be unequivocally established, landscape-scale indices of environmental impact such as EI may prove to be useful indicators of change in microbial communities.