1) When the story of the campaign demands it.
2) When the player quests for it.
3) When it's 10 minutes before the game starts and you don't have any ideas what to throw at the PCs, so you use an instant dungeon generator, put the sword at the center and call it a quest.
All three are prefectly valid times. Some DMs might argue that #1 and #2 have more validity than #3, but then those are the DMs who have their story arcs planned out six months in advance.