Harys Baratheon insulted the honor of House Bolton at one of his many feasts some time around 490 AL. Walton Bolton took grave offense to a remark made about the infamous Red Wedding and responded to the slight by implying that Gianna Martell, the King's recently deceased wife, was unfaithful.
The two men nearly came to blows before Walton stormed out, leaving the capital and calling his bannermen, declaring his house independent from both their Stark liege lord and the Iron Throne. Edmure Stark, who recently assumed the lordship after his father's passing, responded by raising his own forces and marching with the King against the Dreadfort.
The Stark and the Baratheon eventually claimed the castle, and Edmure put all Boltons within to the sword. This brutality would be remembered, and contributed to the Stark lord's gruesome reputation. Unbeknownst to the victors, Walton had managed to sneak two of his children, the twins Bethany and Olyvar, out of the castle before it was overrun.
Edmure Stark's reputation for torture and cruelty was founded from his actions taken during the uprising.