1925 begann Randolph als Gründungspräsident der Brotherhood of Sleeping Car Porters mit der Organisation dieser Gruppe schwarzer Arbeiter und zu einer Zeit, als die Hälfte der verbundenen Unternehmen der American Federation of Labor (AFL) Schwarze von der Mitgliedschaft ausgeschlossen hatte, nahm seine Gewerkschaft in die AFL auf. Trotz Opposition baute er die erste erfolgreiche schwarze Gewerkschaft auf; Die Bruderschaft gewann 1937 ihren ersten großen Vertrag mit der Pullman Company., Im folgenden Jahr entfernte Randolph seine Gewerkschaft aus der AFL aus Protest gegen das Versäumnis, Diskriminierung in ihren Reihen zu bekämpfen, und nahm die Bruderschaft in den neu gegründeten Kongress der Industrieorganisationen (CIO) auf. Anschließend kehrte er zur Frage der schwarzen Beschäftigung in der Bundesregierung und in Branchen mit Bundesverträgen zurück. Er warnte Pres. Franklin D. Roosevelt, dass er Tausende von Schwarzen in einem Protestmarsch auf Washington, DC führen würde., Juni 1941 erließ Roosevelt die Executive Order 8802, die Diskriminierung in der Verteidigungsindustrie und in Bundesbüros verbietet und das Fair Employment Practices Committee einsetzt. Nach dem Zweiten Weltkrieg gründete Randolph die Liga für gewaltfreien zivilen Ungehorsam gegen militärische Segregation, was zur Ausgabe von Pres führte. Juli 1948, der Executive Order 9981, Verbot der Rassentrennung in den Streitkräften.
Als die AFL 1955 mit dem CIO fusionierte, wurde Randolph zum Vizepräsidenten und Mitglied des Executive Council der kombinierten Organisation ernannt., Er war der erste Präsident (1960-66) des Negro American Labor Council, der von Randolph und anderen gegründet wurde, um Diskriminierung innerhalb des AFL-CIO zu bekämpfen.
In einem Echo seiner Aktivitäten von 1941 war Randolph Direktor des Marsches nach Washington für Arbeitsplätze und Freiheit, der am 28. Zwei Jahre später gründete er die A., Philip Randolph Institut für community-Führer zur Untersuchung der Ursachen von Armut. Er litt an einer chronischen Krankheit und trat 1968 von der Präsidentschaft der Bruderschaft der Schlafwagenträger zurück und zog sich aus dem öffentlichen Leben zurück.