Travel mode choice (TMC) prediction aims to identify the potential travel means for individual commuter. The difficulty associated with the TMC prediction is how to make full use of a large number of available factors (or features), and balance the trade-off between the number of selected features and yielded prediction performance. This paper presents a novel feature selection algorithm based on the compressive sensing model, in which candidate features are arranged as a basic dictionary. Features are later ranked and selected based on their contribution to the travel mode. The advantage of the proposed algorithm is two-fold: it is able to select important features that minimize the prediction error; and the feature selection process depends less on the priori domain knowledge. The generality of the proposed algorithm is evaluated using several benchmark classification problems and a real-world household travel survey data. Experimental results demonstrates that the proposed algorithm outperforms state-of-the-art methods via selecting less number of features and achieving the satisfactory classification performance simultaneously.