The flooding of biological data such as genome and protein data derived into in-silico approach has become a prediction tool useful for the scientific community. The exponential growth and availability of fresh annotated protein sequences in the databases motivated us to develop new improved method for identifying Oxygen binding proteins. In this study, we have proposed many approaches, including evolutionary profiles with their cutoff 90% and 50% protein primary sequence similarities for predicting Oxygen binding proteins. Furthermore, the prediction approach results were compared and analyzed by various methods to show the prediction performance. In addition, for optimization of parameters, we have used the dataset size as one of the parameters to achieve the highest accuracy in all methods and it plays an important role to discriminating two classes. The five fold cross validation has been applied to evaluate the performance. The web-server Oxypred2 has been developed for identifying Oxygen binding proteins available at http://bioinfo.imtech.res.in/servers/muthu/Oxypred2/home.html. Our experimental result shows that our approaches are faster and achieve generally a better prediction performance over the existing methods.