Two novel methods for genome wide selection (GWS) were examined for predicting the genetic merit of animals using SNP information alone. A panel of 1,546 dairy bulls with reliable EBVs was genotyped for 15,380 SNPs that spanned the whole bovine genome. Two complexity reduction methods were used, partial least squares (PLS) and regression using a genetic algorithm (GAR), to find optimal solutions of EBVs against SNP information. Extensive internal cross-validation was used tofind the best predictive models followed by external validation (without direct use of the pedigree or SNP location). Both PLS and GAR provided both accurate fit to the training data set for somatic cell count (SCC) (max r = 0.83) and fertility (max r = 0.88) and showed an accuracy of prediction of r = 0.47 for SCC, and r = 0.72 for fertility. This is the first empirical demonstration that genome wide selection can account for a very high proportion of additive genetic variation in fitness traits whilst exploiting only a small percentage of available SNP information, without use of pedigree or QTL mapping. PLS was computationally more efficient than GAR.