The Lost Men are a large organisation of expensive mercenaries operating in the Eastern Lands. They tattoo their skins with maps of the Wushanko Archipelago and are said to be renowned fighters.
Marcus Fine infiltrated the Lost Men with the help of the Claymistress as part of his plan to depose of Tubjub, the villainous khan of Hyu-Ji who was using them to capture sea orphans in order to sell their guts to the soothsayers. This was successful, and Tubjub was exiled in disgrace. Soon enough, however, he struck back and amassed an army of Lost Men in order to attack Hyu-Ji. Upon hearing the news, Fine formulated a plan to create explosives using the island's natural resources - sulphur, charcoal and shell pieces, together making gunpowder - and sailed to Hyu-Ji in order to defend it. This was successful and the Lost Men, along with Tubjub, were obliterated.