To non-destructive detect the damage of column members in frame structures, this study proposes a new method to determine the location and degree of damage, which by using neural network and Rate of modal strain energy change of plane element (PMSECR) based on the damage sample database by an improved uniform design table. This study solves the defect of too few uniform design test points by using orthogonal design to optimize the uniform design table. The two-step method is used to determine the damage location and degree of frame columns. Firstly, to identify the damage location, the PMSECR is taken as damage index, and the representative damage condition is selected as a training sample of General Regression Neural Network (GRNN) by improved uniform test table. Then, after determining the damage location, the Radical Basis Function Neural Network (RBFNN) is used to identify the degree of damage. The effectiveness of the proposed method is verified by numerical simulation and experiments. The identification index of PMSECR overcomes the defect of incomplete modal of structures, and the two-step identification method avoids the defects of non-convergence and a local minimum in the training of neural network. The method can be used to locate the damage location and identify the damage degree of frame columns.