Los primeros esfuerzos de cabildeo para eliminar la segregación en el ejército antes de 1941 no persuadieron al presidente Roosevelt de tomar medidas. El 27 de septiembre de 1940, la primera delegación compuesta por A. Philip Randolph, Walter White (NAACP) y T. Arnold Hill (Liga Urbana Nacional), se reunió con el presidente Roosevelt y sus principales funcionarios. La delegación presentó un memorando en el que se exigía la integración inmediata de todos los negros en las fuerzas armadas. La Casa Blanca emitió una declaración en la que decía: «La política del Departamento de Guerra es no mezclar personal alistado de color y blanco en las mismas organizaciones de regimiento». Las fuerzas armadas no se integraron hasta 1948, bajo la presidencia de Harry S. Truman.
Preocupado porque las reuniones tradicionales no eran efectivas, el 25 de enero de 1941, A. Philip Randolph propuso oficialmente una Marcha sobre Washington para «poner de relieve la cuestión». En los meses siguientes, los capítulos del MOWM comenzaron a organizarse para una marcha masiva programada para el primero de julio de ese año. Durante la primavera, los organizadores estimaron que podrían atraer a 100.000 manifestantes para el evento.
Una semana antes de que se celebrara la marcha, el alcalde de la ciudad de Nueva York, Fiorello La Guardia, se reunió con los dirigentes del MOWM para informarles de las intenciones del presidente de emitir una orden ejecutiva por la que se establecía el primer Comité de Prácticas de Empleo Justas (FEPC) que prohibiría la discriminación en los programas federales de formación profesional y capacitación. Antes de que se firmara la orden, el MOWM exigió también que incluyera una disposición para la desegregación de las industrias de guerra. Roosevelt aceptó y emitió la Orden Ejecutiva 8802, que prohibía la discriminación en los programas federales de formación profesional y capacitación, y en el empleo en las industrias de defensa contratadas por el gobierno. Ante esta importante victoria, Randolph aceptó cancelar la marcha. Continuó con el Movimiento de Marcha sobre Washington como una forma de mantener una organización que pudiera seguir y presionar por el progreso, y hacer que la FEPC cumpliera con su misión.
El MOWM continuó con las concentraciones a lo largo del verano sobre estos temas, pero el punto álgido había pasado. El continuo llamamiento del movimiento a la desobediencia civil no violenta alienó a algunas organizaciones negras, como la NAACP, cuyos líderes les retiraron parte de su apoyo. Aunque se organizó para provocar la marcha sobre Washington de 1941, el MOWM funcionó hasta 1947; sus representantes colaboraron con otros grupos para seguir presionando al gobierno federal. En 1943, Roosevelt emitió la Orden Ejecutiva 9346, que ampliaba la cobertura de la FEPC a las agencias federales más allá de las de defensa.
Randolph siguió promoviendo acciones no violentas para avanzar en los objetivos de los afroamericanos. El futuro líder de los derechos civiles Martin Luther King Jr. y otros hombres más jóvenes se vieron muy influenciados por sus métodos.