The purpose of this paper is to compare the obstacles Japan's representative national trade union centers, Sōhyō and Rengō, faced in their efforts to achieve gender-equal employment and to illustrate how they coped with these obstacles at the time of the enactment of the Equal Employment Opportunity Law in 1985 and at the time of its revision in 2006, through a detailed analysis of primary materials. Thanks to the 1997 revision, labor movements today are free from the dilemma of having to choose either ‘protection’ or ‘equality’ for women. Given this, I argue that the labor movements should now step up their efforts to achieve equality. In order to take a step toward the realization of gender equality and to forge a new solidarity by bridging the chasm that divides the labor movements in different employment categories, reconstructing the present framework of the categories of ‘regular’ and ‘non-regular’ workers is of utmost importance to labor movements.