Mobility and wage labor are two key variables that help to explain some of the complexities of the labor history of colonial Eritrea. Focusing on the initial period of Italian colonization, between the 1880s and 1920s, this article analyzes the relationship between the two above-mentioned variables. Based on previously unexplored archival sources and documents, the authors conclude that wage labor did contribute to the mobility of workers throughout the region (and not vice versa). In the period under consideration, Eritrea did not become a settler colony, despite Italy's initial efforts to import a national labor force. Instead, through a mix of capital investments in construction and transport, and increasing military recruitment, the Italian regime contributed significantly to an increase in free wage labor in the region. Within a year of Italy's 1911 invasion of Libya, it needed to reinforce its colonial army. From 1912 onward, in return for wages, tens of thousands of Eritreans entered the Italian colonial army to fight on the Libyan front. This military employment left voids in the local labor market, which were filled by people from neighboring countries, particularly Ethiopians and Yemenis. A relationship thus developed and continued between mobility and wage labor.