Thing is, that's not it. "King of Thieves" is a singular noun phrase, which complicates things a bit.
But, yeah, definitely "Thieves'."