The performance of a learning-based method highly depends on the quality of a training set. However, it is very challenging to collect an efficient and effective training set for training a good classifier, because of the high dimensionality of the feature space and the complexity of decision boundaries. In this research, we study the methodology of automatically obtaining an optimal training set for robust face detection by resampling the collected training set. We propose a genetic algorithm (GA) and manifold-based method to resample a given training set for more robust face detection. The motivations behind lie in two folds: (1) dynamic optimization, diversity, and consistency of the training samples are cultivated by the evolutionary nature of GA and (2) the desirable non-linearity of the training set is preserved by using the manifold-based resampling. We demonstrate the effectiveness of the proposed method through experiments and comparisons to other existing face detectors. The system trained from the training set by the proposed method has achieved 90.73% accuracy with no false alarm on MIT+CMU frontal face test set—the best result reported so far to our knowledge. Moreover, as a fully automatic technology, the proposed method can significantly facilitate the preparation of training sets for obtaining well-performed object detection systems in different applications.