Die "Brotherhood of Sleeping Car Porters" wurde 1925 von A. Philip Randolph und anderen gegründet. Es war die erste rein afroamerikanische Gewerkschaft der Nation. Die neue Gewerkschaft stand der Opposition ihres Arbeitgebers George Pullman und der Pullman Company, einem Unterstützer von Booker T. Washington, und den Handwerksgesellschaften gegenüber. Obgleich William Green, der Kopf der "American Federation of Labor" (AFL), die Bemühungen der Bruderschaft unterstützte, erklärten die "Hotel and Restaurant Employees International" ihre Zuständigkeit für die Schaffner. Der Gewerkschaft empfing jedoch keine internationale Charter bis 1936.
1937 schloß die Pullman Company und die Bruderschaft den ersten Vertrag mit einer schwarzen Gewerkschaft, der einige der seit langem bestehenden Forderungen des Anschlußes befriedigte. Er bewilligte eine Verringerung der Zahl der Arbeitsstunden, eine Lohnerhöhung, Arbeitsplatzsicherheit und die offene Ausübung der Gewerkschaft.
Schließlich wurde die Gewerkschaft für seine Arbeit für die Zivilrechte bekannt. Ab 1934 sprach sein Präsident Randolph auf jeder AFL-Tagung und rief zur Integration von Schwarzen in der Arbeiterbewegung auf. Von seiner Position in der AFL aus und nach 1960 als Führer des "Negro American Labor Council", kämpfte Randolph für Rechte der schwarzen Leute. Gegen den Ausschluß von Schwarzen aus der Kriegsindustrie organisierte er den ersten Marsch auf Washington von 1941, der Präsidenten Franklin D. Roosevelt veranließ, eine Order der Ächtung der Deskriminierung von Schwarzen bei der Kriegsindustrie und bei öffentlichen Anstellungen zu erlassen sowie das "Fair Employment Practices Committee" einzusetzen, um zu verhindern das sich tausende Afro-Amerikaner in die Hauptstadt der Nation versammelten.
>In den 50ern wurde Randolph erster schwarzamerikanischer Vizepräsident der AFL und zwanzig Jahre später waren er und die Bruderschaft auch an der Spitze des Marsches auf Washington (1963).