Deciphering three dimensional structure of a protein sequence is a challenging task in biological science. Protein fold recognition and protein secondary structure prediction are transitional steps in identifying the three dimensional structure of a protein. For protein fold recognition, evolutionary-based information of amino acid sequences from the position specific scoring matrix (PSSM) has been recently applied with improved results. On the other hand, the SPINE X predictor has been developed and applied for protein secondary structure prediction. To date, several methods for protein fold recognition have been developed but with limited recognition accuracy only. In this paper, we have developed a strategy of combining evolutionary-based information (from PSSM) and predicted secondary structure using SPINE X to improve protein fold recognition. The strategy is based on finding the probabilities of amino acid pairs (AAP). The proposed method has been tested on several protein benchmark datasets and an improvement of 8.9% recognition accuracy has been achieved. We have achieved, for the first time over 90% and 75% prediction accuracies when the sequential similarity rate is less than 40% and 25%, respectively. We report 90.6% and 77.0% prediction accuracies, respectively, for the Extended Ding and Dubchak benchmark, and Taguchi and Gromiha benchmark that have been widely used for protein fold recognition in the literature.