We have developed new methods for automatically identifying landmarks such as craters, gullies, dark slope streaks, and dust devil tracks in remote sensing imagery. These methods are based on statistical measures of local terrain salience. The salience of a region is defined as the degree to which it differs from its surrounding context. We use pixel intensity histograms to represent each candidate region, and we compute salience in one of two ways. The first method calculates the Kullback-Leibler divergence between the region’s histogram and a larger enclosing region. The second method calculates the entropy of the region’s histogram independently. The KL-divergence approach is useful for detecting unusual landmarks, while the entropy approach detects high-contrast features such as ridges and crater edges. We have automatically identified landmarks in several Mars surface images collected from orbit (MOC and THEMIS data) and evaluated them against manual annotations of dark slope streaks and dust devil tracks. We have also trained a landmark machine classifier that can assign new landmarks to one of several categories. In an evaluation on dark slope streaks, dust devil tracks, and craters, the classifier achieved an accuracy of 93%. Further, because detections are made based on a generic notion of salience, they are not restricted to known landmark types. It is possible to identify landmarks that do not fit into any existing category as novel features, enabling scientific advances that otherwise rely on serendipity to bring them to light. Automated landmark identification can be useful both onboard a remote spacecraft and in ground-based processing on the Earth. In an onboard setting, salient landmarks can be detected and catalogued as they are observed, providing a highly compressed summary of the region under study (e.g., “five craters, two gullies, and 37 sand dunes” along with their locations). On the ground, gigabyte archives of past images can be analyzed and annotated with meta-data indicating the existence and location of different landmark types. These annotations can enable a content-based search facility that will permit the easy retrieval of images that contain a specific feature of interest.