The accuracy of computer-aided diagnosis (CAD) for early detection and classification of breast cancer in dynamic contrast-enhanced magnetic resonance imaging (DCE-MRI) is dependent upon the features used by the CAD classifier. Here, we show that fast orthogonal search (FOS), which provides a more efficient iterative manner of computing stepwise regression feature selection, can select features with predictive value from a set of kinetic and texture candidate features computed from dynamic contrast-enhanced magnetic resonance images. FOS can in minutes search candidate feature sets of millions of terms, which may include cross-products of features up to second-, third- or fourth-order. This method is tested on a set of 83 DCE-MRI images, of which 20 are for cancerous and 63 for benign cases, using a leave-one-out trial. The features selected by FOS were used in a FOS predictor and nearest-neighbour predictor and had an area under the receiver operating curve (AUC) of 0.889 and 0.791 respectively. The FOS predictor AUC is significantly improved over the signal enhancement ratio predictor with an AUC of 0.706 (p = 0.0035 for the difference in the AUCs). Moreover, using FOS-selected features in a support vector machine increased the AUC over that resulting when the features were manually selected.