This paper presents a performance comparison of several state-of-the-art visual feature extraction algorithms when applied in a poorly-structured environment as found on the planet Mars. So far, no systematic evaluation of feature extraction algorithms in extraterrestrial environments is available. The algorithms in this paper are evaluated using the Devon Island dataset which is said to have one of the most Mars-like environments on Earth. The ground truth for the performance comparison is based on a location retrieval task using the GPS data provided by the dataset. A range of common feature detection and description algorithms is covered including floating point and binary descriptors. With the aim of efficient image retrieval the descriptor vectors are quantized in a bag-of-words model using the k-means algorithm. The results show that the well-known SURF feature provides superior performance over other state-of-the-art feature extraction algorithms in a Mars-like environment.