In this book, I present an improved scatter search (SS) algorithm for predicting all-atoms protein structures using the CHARMM22 energy model. My algorithm produces a 3D structure of the whole protein by minimizing the energy function linked to protein folding. This is based on a sequence of amino acids as well as on data collected from known protein structures for comparative purposes. Defined as an evolutionary algorithm, SS relies on a population of candidate solutions. Candidate solutions, over a number of iterations, experience evolutionary operations which combine intense search and diversification. My algorithm is evaluated on few proteins, whose structure is defined in a Protein Data Bank (PDB). The results generated by the improved SS algorithm are compared with those of other energy models. The results showed that my algorithm produces 3D structures with good and promising root mean square deviations from the reference proteins. This study also demonstrates the advantage of the CHARMM22 energy model.