1850, "like a mere trace of what has been," originally in biology, from vestige + -al (1).
Entries linking to vestigial
vestige n.
c. 1600, from French vestige "a mark, trace, sign" (16c.), from Latin vestigium "footprint, trace," a word of unknown origin.
-al 1
suffix forming adjectives from nouns or other adjectives, "of, like, related to, pertaining to," Middle English -al, -el, from French or directly from Latin -alis (see -al (2)).