Little has been revealed about the past of the man known as Crossbones. A mercenary and assassin, Crossbones can often be seen doing the dirty work of the Red Skull, but will work for anyone with a big enough wallet. While not out on missions, Crossbones can be found teaching the latest generation of villains at Taskmaster's School for Criminals. As a mercenary, he enlisted with the communist Red Skull (Albert Malik) in Algeria, serving him as "Frag" until he was sent to invade Arnim Zola's Switzerland chateau. Ultimately the only team member to survive the assault, Rumlow there met and impressed the Nazi Red Skull (Johann Schmidt); this Skull accepted Brock’s services, code-naming him “Crossbones.” Sent to retrieve the five Bloodstone fragments of Ulysses Bloodstone, Crossbones shadowed Baron Helmut Zemo's search for them. While Zemo battled Captain America, Crossbones knocked out Captain America's pilot, John Jameson, and stole two Bloodstone fragments; when he got near the other three, the five combined to re-animate Baron Heinrich Zemo's corpse under control of the alien Hellfire Helix. Unobserved, Crossbones destroyed the Helix (worn on the corpse's forehead) with a crossbow bolt. Brock then kidnapped Captain America's ally Diamondback (whom he recognized as Rachel Leighton), using her as bait to trap Captain America; but when the Skull learned of Crossbones' involvement with the Captain, he ordered Crossbones to flee.