The word vestigial means a "functionless remnant", and the word vestige means "a remnant" of something rare or extinct, so it's not surprising in the least that the former word derives from the latter. Vestige, which was borrowed into English at the beginning of the seventeenth century from French, traces to the Latin word vestigium, which literally meant "a footprint" but had figurative connotations of a trace left somewhere, which is how we got the word. This does not have a fully understood origin, per se; however, etymologists theorize that it either derives from the Proto-Indo-European root steygh, meaning "to walk", or from PIE wers, which literally meant "drag along the ground" (and would have come through Latin verro, "to sweep"). Ironically, both the words vestige and vestigial have been decreasing dramatically in use since the 1950s, and all we see of them now is a mere vestige.
Adam Aleksic, a rising sophomore studying linguistics and government at Harvard University, has been described as the internet's sixth most famous etymologist. He also has disturbing interests in politics, vexillology, geography, board games, conlanging, and law.