To increase accuracy and efficiency of terrain labeling in agricultural environment, a method based on Iterative-RELIEF was proposed. In this method, training samples were generated by super-pixel segmentation, and then the feature selection algorithm Iterative-RELIEF output a feature weight vector with its elements representing to which extent the corresponding feature influenced the results of terrain labeling. A large amount of irrelevant features were discarded by setting the feature weight threshold. In the labeling experiment over DARPA datasets, the proposed method not only raised the accuracy of ground labeling and the recall rate of obstacle labeling by 1% and 0.8%, respectively, but reduced the computational complexity of the SVM terrain classifier by about 40%. In the navigation experiment, the method increased the efficiency of the agricultural robot by about 15%. 