In 1952, A. Philip Randolph, the head of America’s largest black union and a prominent civil rights campaigner, traveled to Japan and Burma funded by the American Committee for Cultural Freedom. In Asia, he encountered socialists and trade unionists struggling to negotiate the fractious divides between communism and capitalism within postwar states. In Burma, in particular, Western powers, the Soviet bloc, and powerful Asian neighbors used propaganda, aid missions, and subsidized travel to offer competing visions of development while accusing each other of new forms of imperialism and foreign interference. In such an environment, a battle for hearts and minds within Asian labor movements constituted the front lines of the early years of the Cold War. Randolph’s journey shows us how Asian socialists and trade unionists responded to powerful foreign interests by articulating an early sense of non-alignment, forged in part through emerging Asian socialist networks, well before this was an official strategy. The Asian actors with whom Randolph interacted in Japan and Burma mirrored his own struggles as a socialist, a trade unionist, and a “railway man” while furthering his campaign for civil rights at home. This article uses Randolph’s journey to examine parallels and divergences between African-American and Asian socialists and trade unionists during the early Cold War, an age characterized by deepening splits in the politics of the Left.