The more recent possible origin for the phrase is an incident said to have taken place during the siege of the Alamo in 1836, when William Barret Travis drew a line in the sand with his sword and urged those willing to stay and defend the fort to step across it. Unfortunately, this heroic story seems to have been invented by a 19th century promoter long after the fall of the Alamo. But the myth itself probably greatly popularized the phrase, so it does count as an origin of sorts even if the incident itself was apocryphal.
Another possible origin dates back to the time of the Roman Empire. It seems that one of the Macedonian kings, a bit short of cash, decided to invade Egypt, then a Roman protectorate. His army was met at the border by a lone Roman senator named Popillius Laenas, who ordered the king to withdraw. The king began to stall for time, so Popillius Laenas drew a circle in the sand around the king and demanded that the king agree to withdraw his army before he stepped out of the circle. The king, apparently impressed by the senator's nerve (or, more likely, by the Roman Empire in general), withdrew. Incidentally, not only is this account verified by contemporary historians, but it also may be the only known instance of a line drawn in the sand actually stopping someone.