Enlisted men were an essential source of labor in the nineteenth-century United States. Troops built infrastructure, surveyed and scouted territory, and provided services to private companies, especially railroads. They contributed in significant ways to the expansion of private investment and the extension of state power across the trans-Mississippi West. Yet soldiers have been largely absent from US labor history. This essay examines the American military labor regime and the resistance it engendered. It explores the unfree nature of military labor and its distinctiveness from “free labor” in the late nineteenth century. It also shows how soldiers challenged this labor regime. Through protest, petition, and desertion, they tried to set limits on their own exploitation. The story of these “enlisted laborers” highlights the significance of unfree military labor in the nineteenth century. It also suggests the need for more attention to the labor history of the military.