We present an approximation algorithm for the problem of partitioning the vertices of a weighted graph into p blocks of equal size so as to maximize the weight of the edges connecting different blocks. The algorithm is based on semidefinite programming and can in some sense be viewed as a generalization of the approximation algorithm by Frieze and Jerrum for the Max Bisection problem. Our algorithm, as opposed to that of Frieze and Jerrum, gives better performance than the naive randomized algorithm also for p > 2.