Species richness and species rarity have been identified as important criteria when selecting conservation areas. Traditional approaches that choose sites based solely on local species richness often fail to protect those species most at risk. By assessing the representation of species across a network of sites, the protection of all species is more likely to be assured. A GIS approach based on the Maximal Covering Location Problem (MCLP) is compared to existing complementarity algorithms using data collected by the British Trust for Ornithology on the distribution of birds in Wales, UK. Despite a range of solutions depending on the algorithm used, the results presented here suggest that the overall pattern of species and the habitats with which they are associated remain largely unchanged. Community ordination is used to examine the species composition of sample units and to relate this to habitat composition. This shows that key marine, coastal and moorland sites are selected by most solutions while there is a greater degree of substitutability for sites that are predominantly woodland and farmland. The GIS-based MCLP approach is then extended by incorporating various priority weightings, considered in terms of conservation criteria relevant to birds in Wales.