This paper proposed an enhanced NEH with full insertion moves to solve the permutation flow shop problem. The characteristics of the original NEH are investigated and analyzed, and it is concluded that the given method would be promising to find better solutions, while the cost would be increased. Fast makespan calculating method and eliminating non-promising permutation policy are introduced to reduce the evaluation effort. The former decreases the time complexity from O(n4m) to O(n3m), which is an acceptable cost for medium and small size instances considering the obtained solution quality. The results from computational experience show that the latter also can eliminate a lot of non-promising solutions.