Nieuw Haarlem was the largest city of the Netherlands' colony in Terranova. Pirate Red Rodney Radcliffe attacked Nieuw Haarlem in the mid 17th century. During the course of the attack, he stormed governor Piet Kieft's residence as he was preparing to have sexual intercourse with a woman named Katrina. Kieft jumped from his second story window to escape Radcliffe. Worse still, Radcliffe kidnapped Kief's cook, Cornelius, and refused a ransom for his return.

Kieft, desperate for revenge, agreed to combine his forces with those of Atlantis and England to destroy the Avalon pirates.