The graph coloring problem as one of the popular NP-hard problem in graph theory. There are many heuristic algorithms to solve this problem, but they all suffer from poor quality of solution and long computation time. The membrane evolution algorithm proposed in recent years has shown unique advantages in dealing with NP-hard problems. Based on the membrane evolutionary algorithm framework, a membrane evolution algorithm is proposed to solve the graph coloring problem by combining the graph coloring problem and membranes, and six membrane evolution operators are designed for copy, fusion, division, cytolysis, fusion_ division, and taboo search. These operators evolve the membranes and membrane structures as they evolve to find more optimal solutions and finally solutions. Experiments were conducted on 40 challenge datasets of DIMACS, and the results were compared with those of three latest algorithms, which can effectively reduce the solution time while guaranteeing the solution quality, with 58% of the instances prevailing.