Abstract: Gene Expression Programming is effective for function mining. In gene expression usually exist some un-expressed introns. To improve the expression efficiency, this paper makes following contributions: Proposed an evolutionary algorithm embedded gene expression programming (EGEP) based on a new decoding method of gene; Proposed some new concepts, i.e. the maximum expression tree, nested expression tree and spliced expression tree; Analyzed the expression space of gene and the complexity of algorithm. Extensive experiments show that the success rate is improved greatly and under the small size population, the ability of mining function surpasses GEP apparently. In single gene algorithms, when the objective functions are bivariate function and single-variable function, the ratios of the convergence generation of EGEP to that of GEP are 25.5% and 16.3% respectively; compared with GEP, the success rate of EGEP is averagly increased by 43% in bivariate function mining.