1. Art Description
Here were the instructions given to Mark for the project:
"This card should show a barbarian with grafted-on body parts that work, but obviously came from other creatures. He is obviously corrupted and 'enhanced' by the Cabal, and should be shown in a pose that shows this and enhances the alien body parts."
2. Sketches
Mark took that art description and came up with this initial sketch:
Here we can see the patched-together nature of this barbarian; he's got horns, a tail, some extra appendages growing off his shoulders, and an entirely new set of legs. It even appears that his right hand is itself made of two fused-together hands. That's what you get when you work for the Cabal.
The sketch captured the art team's vision quite well -- perhaps too well! They wanted to make sure it was clear that this was once a human being; the barbarian's head in particular looked a little too monstrous, almost minotaurish.
3. Final Art
Here's Barbarian Outcast's final art. You can see that the horns have been scaled back and the barbarian's face and nose shape have become more human. Tedin took the opportunity to tweak the figure's equipment: the axe is noticeably more fantastic-looking, and he's gained a matching right gauntlet (pity we can't see his double right hand as well anymore).
As you see the final card below, note how the art was cropped for the sake of fitting on the card. Since the original art was roughly square and Magic art is wider than it is tall, the barbarian's front foot had to be cut off.
4. Card
Finally, here is the card as you can see it in booster packs.