The Binding Stone was a construct of the Horadrim, used to bind the Prime Evil Baal after Tal Rasha took it upon himself to use his body as a living soulstone. Etched with runes of containment, it was held fast to the walls of a chamber in a tomb deep below the sands of Aranoch. Tal Rasha ordered his breathren to chain him to the stone, where he was left to wrestle with Baal's spirit for all eternity.
His imprisonment was broken by the Dark Wanderer and Marius, who imprisoned Tyrael in Baal's place (possibly indicating that the Stone can bind any entity, not just Prime Evils). The archangel was rescued by a group of heroes however.
Visually, the Stone is a large obelisk of brown-gray rock, carved with runes and glimmering with power as the imprisoned entity is struggling to break its grip. It was, apparently, made on the spot, as a makeshift addition to the damaged soulstone.