Well, maybe not a true "legend" at that point, but Mr. Perfect came pretty close a few years back as a surprise entrant.
Yep, 2002. He was one of the last three in the match with Kurt Angle and Triple H. I think he actually eliminated Steve Austin.
I was marking out like crazy for Perfect here.