1650s, "trick, illusion, imposture" (senses now obsolete), from French prestige (16c.) "deceit, imposture, illusion" (in Modern French, "illusion, magic, glamour"), from Latin praestigium "delusion, illusion" (see prestigious).
From about 1815 it was used in the sense of "an illusion as to one's personal merit or importance, a flattering illusion," hence, positively, "a reputation for excellence, importance, or authority," senses probably introduced from French, often in reference to Napoleon:
When the same question was put to those who knew him and France best, they answered, 'that a peace dictated in France would have undone him ;'—'that his throne was founded on public opinion,' and 'that if the prestige,' for so they called it, 'of his glory were to be destroyed, the state of his affairs, and the character of the French people forbade him to expect that his power would long survive it.' ["Memoirs of Bonaparte's Deposition," Quarterly Review, Oct. 1814]