Рэндольф начал карьеру с переезда. В апреле 1911 года он перебрался из Флориды в Гарлем. Он стал завсегдатаем любительских театров; казалось, с его красноречием и харизмой его путь лежит прямиком в серьезные драматические актеры, но родители этому воспротивились. Некоторое время он проучился в Городском колледже Нью-Йорка, где запоем читал Карла Маркса. Рэндольф участвовал в основании нескольких журналов для чернокожих и так познакомил это сообщество с марксизмом. В одной из редакторских статей он назвал русскую революцию «величайшим достижением XX века». Рэндольф выступал против участия США в Первой мировой войне, будучи глубоко убежден, что война служит только интересам производителей оружия и других промышленников. Он объявил кампанию против движения Маркуса Гарви, призывавшего чернокожих американцев переселяться на историческую родину, в Африку. В разгар этой борьбы Рэндольф получил коробку с отрезанной человеческой рукой и запиской с угрозами.

В это время его несколько раз арестовывали за нарушение запрета на антиправительственную агитацию, однако в личной жизни он становился все более буржуазным и респектабельным. Рэндольф женился на благовоспитанной женщине из уважаемого гарлемского семейства. По воскресеньям после обеда они с удовольствием участвовали в еженедельных променадах. Люди наряжались — краги, трости, бутоньерки, гамаши, необычные шляпы — и гуляли по Ленокс-авеню или 135-й улице, обмениваясь приветствиями и любезностями с соседями.

К началу 1920-х Рэндольф начал сотрудничать с организациями рабочих. Он помог основать полдюжины небольших профсоюзов, объединив официантов, работников кухни и другие группы, не охваченные профсоюзами раньше. В июне 1925 года к Рэндольфу обратились несколько проводников пульмановских вагонов, которые искали харизматичного и образованного лидера, чтобы помочь им основать профсоюз. Pullman Company производила спальные вагоны класса люкс и сдавала их в аренду железнодорожным компаниям. Клиентов обслуживали несколько смен чернокожих слуг в ливреях: они чистили обувь, перестилали постели и подавали на стол. После Гражданской войны в США основатель компании Джордж Пульман стал нанимать на эти места бывших рабов, рассчитывая получить безропотных и покорных работников. Проводники пытались объединиться в профсоюз еще в 1909 году, но компания всякий раз давала им отпор.

Рэндольф взялся за дело и следующие 12 лет посвятил созданию профсоюза проводников и получению на него разрешения от компании. Он ездил по всей стране, убеждая проводников вступить в профсоюз, и это в то время, когда за малейший намек на профсоюзную активность работника могли избить или уволить. Главным орудием Рэндольфа были его манеры. Один из членов профсоюза вспоминал: «Он захватывал. Только совершенно бесчувственный человек мог от него отвернуться. Рядом с ним ты чувствовал себя как апостол рядом с Учителем. Это не сразу давало о себе знать, но, вернувшись домой, ты обдумывал услышанное и понимал, что просто должен следовать за ним, вот и все».

Дело продвигалось медленно, но за четыре года численность профсоюза выросла почти до семи тысяч членов. Рэндольф обнаружил, что рядовым сотрудникам не нравилось, что он критикует компанию, которой они оставались преданны. Они не разделяли его критического отношения к капитализму, и он сменил тактику. Рэндольф объявил борьбу за достоинство. Кроме того, он принял решение отвергать любые пожертвования от сочувствующих белых. Эту победу чернокожие должны были обеспечить и завоевать своими силами.

А потом началась Великая депрессия, и компания нанесла ответный удар, увольняя сотрудников, которые голосовали за забастовку, или угрожая им. К 1932 году число членов профсоюза сократилось до 771. Представительства профсоюза в девяти городах закрылись. Рэндольфа и сотрудников его штаба выселили из конторы за неуплату аренды. Зарплата самого Рэндольфа, десять долларов в неделю, упала до нуля. Всегда безупречно одетый и элегантный, теперь он ходил в обносках и лохмотьях. Профсоюзных активистов избивали повсюду, от Канзас-сити до Джексонвилля во Флориде. В 1930 году за месяц до смерти Дэд Мур, сторонник движения из Окленда, написал убежденное письмо: