Оказавшись в декабре 1914 года в Александрии, Трумпельдор сразу наладил контакты с высланными еврейскими поселенцами, среди которых было много его друзей по охранным формированиям "а-Шомер" (Страж). Им было ясно, что бессмысленное сидение в лагере беженцев не отвечает интересам сионизма.
Положение Иосифа выгодно отличалось от других беженцев, запертых в бараки лагеря "Мафруз". Сразу по приезду в Александрию его нашел тамошний русский консул Петров, сообщивший ему, что как русский офицер Трумпельдор может получать положенную ему пенсию ежемесячно в консульстве.
Через русского консула на Трумпельдора вышел Владимир-Зеев Жаботинский, оказавшийся в Александрии в качестве корреспондента газеты "Русские Ведомости". Жаботинский первым предложил руководству Всемирной Сионистской организации подумать об организации еврейского воинского формирования в составе британских войск, действовавших на Ближнем Востоке.
Вскоре состоялась встреча Жаботинского и Трумпельдора. Иосиф немедленно поддержал инициативу своего нового единомышленника. Эта встреча положила начало сотрудничеству этих двух замечательных людей и лидеров. Так зародилась идея Еврейского Легиона.
На собрании высланных еврейских поселенцев в бараке лагеря "Мафруз" было принято историческое решение о создании еврейского полка, которому предстояло сражаться за освобождение Земли Израиля от турецкого владычества.
Теперь предстояло заручиться поддержкой британского командования, под начало которого должен был встать еврейский полк.
С этой целью еврейская делегация, в составе которой были Трумпельдор и Жаботинский, 5 марта 1915 года встретилась с командующим британскими войсками в Египте генералом Максвеллом. Здесь их ждало полное разочарование — британский генерал, уважительно глянув на Георгиевские кресты Трумпельдора, тем не менее отказался принять еврейскую воинскую часть в вверенные ему войска. Генерал объяснил это тем, что на службу Его Величеству могут быть приняты только британские подданные.
Как альтернативу Максвелл предложил сформировать из еврейских добровольцев военно-транспортную часть, которую предполагалось использовать на фронте против Турции. Такое предложение британцев было неожиданным и вызвало сомнения у членов еврейской делегации. Только Трумпельдор решительно поддержал идею еврейского военно-транспортного отряда: "Окопы или транспорт — большого различия тут нет. И те, и те — солдаты, и без тех и без других нельзя обойтись; да и опасность часто одна и та же".
На возражение, что тем самым откладывается освобождение Страны Израиля, Иосиф ответил: "И это не так существенно, рассуждая по-солдатски. Чтобы освободить Палестину, надо разбить турок. А где их бить, с юга или с севера, это уж технический вопрос. Каждый фронт ведет к Сиону".
Не откладывая дела в долгий ящик, Трумпельдор вместе с британским полковником Джоном Генри Паттерсоном приступил к формированию еврейского военно-транспортного отряда, получившего название Сионского транспортного корпуса. Уже в конце марта главный раввин Александрии Рафаэль Делла Пергола принял присягу у 650 еврейских добровольцев, записавшихся в Сионский корпус. Над солдатским строем реяло знамя Сионского корпуса с шестиконечной Звездой Давида, такие же эмблемы украшали солдатские мундиры.
Полковник Джон Генри Паттерсон, ирландец, профессиональный военный, глубоко понимавший цели еврейского национально-освободительного движении, был назначен командиром Сионского корпуса. Впоследствии полковник Паттерсон опубликовал книгу "С сионистами в Галлиполи", где дал высокую оценку мужеству еврейских солдат. Трумпельдор, получивший к тому времени звание капитана британской армии, стал его заместителем.
После пятнадцати дней интенсивной боевой подготовки в британском военном лагере Сионский корпус в составе 650 еврейских бойцов отплыл на кораблях из Александрии. На набережной при огромном стечении народа состоялись торжественные проводы. Корабли с военнослужащими Сионского корпуса взяли курс на греческий остров Лемнос. Там корпус был включен в состав ударной войсковой группы, которая готовилась к вторжению на полуостров Галлиполи.
Целью Дарданелльской операции было овладеть проливами Дарданеллы и Босфор, взять Константинополь и принудить Турцию выйти из войны на стороне Германии. Сражение за Галлиполи — одно из самых трагических событий Первой мировой войны. Оно продолжалось девять месяцев и обернулось катастрофой для британской армии. Число потерь превысило 200 тысяч убитыми и ранеными.