Summary: Nature reserve site selection has become critical as the human population grows and environmentalists seek ways to preserve species and their natural habitats. Simple tabu searches are developed and tested for two reserve site selection models-the maximal covering species problem and the maximal expected covering problem. The testbed is an Oregon terrestrial vertebrate data set composed of 426 species and 441 hexagonal sites. In addition, an extension to a linearized version of the maximal expected covering problem is proposed and tested.