Legacy code is based on the phrase of a legacy system that specifically applies to code. According to Wikipedia it probably dates back to the 1970s and was in common usage in the 1980s. It took off with the tech explosion of the 1990s.
This can be seen with Google's ngram viewer: legacy system,legacy code
Digging into this further, you can find documented uses of the term 'legacy system' in the 1970s.
The earliest example of 'legacy system' that google has is in a book on Proceedings of the Army Numerical Analysis and Computers Conference from 1978:
... well strutted and documented solution to a clearly defined problem is the legacy system operation needs to be understood and to change the existing system with confidence.
There is also an example of 'legacy system' being used outside of the technology industry in Clout: Womanpower and Politics grin 1976:
... in addition, she holds a seat as the third-ranking Democrat on the powerful Banking and Currency Committee - positions of power she has built up on her own, not via the legacy system.
Beyond these example which shows its use has extended beyond the pure software world, the specifics of where exactly the term originated are probably lost to the sands of time. Given the military and political references, it may have originated with them (primarily the military and its jargon migration ("It seems likely that 'kluge' came to MIT via alumni of the many military electronics projects run in Cambridge during the war (many in MIT's venerable Building 20, which housed TMRC..."))