The Stepstones are a group of islands located east of Dorne and just west of the coast of Essos (in particular, the region known as the Disputed Lands). According to myth, Westeros and Essos were once joined by a great land-bridge, across which the First Men invaded Westeros. The Children of the Forest destroyed the land-bridge with magic more than ten thousand years ago, leaving behind only the shattered islands as evidence of its passing.
Today the Stepstones mark the border between the Narrow Sea to the north and the Summer Sea to the south. There are eight large and numerous smaller islands in the chain, with the Free City of Tyrosh located on the north-eastern-most island in the chain. Pirates, freesails and mercenaries rule over and plague the Stepstones, making it difficult to establish any kind of outside rule there.
In the books
In the A Song of Ice and Fire novels, it is related that at least one of the Stepstones was conquered by Maelys the Monstrous, one of the Blackfyre Pretenders, in the War of the Ninepenny Kings, as a staging area for an invasion of Westeros. King Jaehaerys II sent an army to destroy his forces before they were ready, and Maelys Blackfyre was killed in battle by Ser Barristan Selmy. Attempts by both the Seven Kingdoms and the Free Cities to conquer all of the Stepstones have failed.
Two of the islands in the Stepstones chain are Bloodstone and Grey Gallows.