Fitness Distance Correlation (FDC) can hardly predict the evolution difficulty of Gene Expression Programming (GEP) because problems with different hardness would result in very similar FDC values in GEP. To solve the problem, the authors propose a posture model and region density to predict GEP’s evolution difficulty. This study made the following contributions: (1) It introduces the concepts of the chromosomes’ distance and posture model in GEP; (2) It proposes region density of a posture model; (3) It proves that the posture model is a mapping from the original searching space, and the mapping preserves the population’s dynamic migration property in the original searching space; (4) It demonstrates the validity of using posture model and region density to predict GEP’s evolution difficulty; (5) It conducts extensive experiments to show that the new model can precisely predict the evolution difficulty of GEP.