One feature of riparian zones is their ability to significantly reduce the nitrogen loads entering streams by removing nitrate from the groundwater. A novel GIS model was used to prioritise riparian rehabilitation in catchments. It is proposed that high-priority areas are those with a high potential for riparian denitrification and have nearby land uses that generate high nitrogen loads. For this purpose, we defined the Rehabilitation Index, which is the product of two other indices, the Nitrate Removal Index and the Nitrate Interception Index. The latter identifies the nitrate contamination potential for each raster cell in the riparian zone by examining the extent and proximity of agricultural urban land uses. The former is estimated using a conceptual model for surface–groundwater interactions in riparian zones associated with middle-order gaining perennial streams, where nitrate is removed via denitrification when the base flow interacts with the carbon-rich riparian sediments before discharging to the streams. Riparian zones that are relatively low in the landscape, have a flat topography, and have soils of medium hydraulic conductivity are most conducive to denitrification. In the present study, the model was implemented in the Tully–Murray basin, Queensland, Australia, to produce priority riparian rehabilitation area maps.