AbstractIn this paper we describe almost all edge‐colored complete graphs that are fully symmetric with respect to colors and transitive on every set of edges of the same color. This generalizes the recent description of self‐complementary symmetric graphs by Peisert and gives examples of permutation groups that require more than 5 colors to be represented as the automorphism group of a k ‐colored graph. This also contributes to the recent study of homogeneous factorizations of complete graphs. The result relies on the classification of finite simple groups. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 329–345, 2009