בסתיו 1909 יזם ישראל שוחט את הקמתו של 'לגיון העבודה', שכונה בקיצור 'עבודה' כדי למנוע קונוטציות צבאיות. ב-19 בספטמבר 1909 באסיפה השנתית השניה של ארגון 'השומר' שנערכה בחיפה התקבלה ההחלטה על הקמת 'הלגיון'. שוחט חיבר את התקנון של הארגון החדש, שנועד להיות זרוע נוספת של ארגון 'בר גיורא' בדומה לארגון 'השומר'. לגיון העבודה היה ארגון צבאי למחצה ומחתרתי למחצה. מטרתו היתה לפעול לפעול לכיבוש העבודה ולסייע לכיבוש השמירה. חברי הלגיון התחייבו לשרת במסגרתו במשך שנתיים שבהן יהיו מחוייבים למשמעת צבאית ולקיום אורח חיים שיתופי עם החברים האחרים. בתקופת שרותם בארגון היה על החברים לבצע עבודות כיבוש של שטחי קרקע חדשים, לבצע משימות עבודה קשות, לקלוט עולים חדשים ולהכשירם לחיי עבודה, כיבוש ושמירה. ההכנסות מעבודת חברי 'הלגיו' נכנסו לקופה כללית משותפת, שממנה סופקו כל צרכי החברים.

'לגיון העבודה' הקים שתי קבוצות עבודה אחת בחוות סג'רה ואחת בחדרה. הקבוצה שפעלה בסג'רה התפזרה כעבור כשנה בשל חיכוכים עם הפועלים האחרים ובשל שביתה שפרצה בחוות סג'רה. חלק מהם השתתפו בעליה על אדמות אום ג'וני ובהקמת דגניה. הקבוצה שפעלה בחדרה תרמה רבות לכיבוש העבודה העברית בחדרה ובישובים הסמוכים.

במפלגות הפועלים התעוררה התנגדות לפעילותו של 'לגיון העבודה'. 'הפועל הצעיר' אסרה על חבריה להצטרף ללגיון בשל הגינונים הצבאיים שרווחו בו ומפני שלשון הדיבור בו היתה יידיש. 'פועלי ציון' התנגדו למעטה הסודיות שבבסיסו של הארגון ודרשו לקבל דיווח מלא על הפעילות. היו קשיים בגיוס חברים ורבים נרתעו מהצורך להתחייב לשנתיים ולחיות במשמעת צבאית. כעבור כשנה של פעילות התפזרו החברים ו'לגיון העבודה' חדל להתקיים.