Born on February 15, 1964, in Lynchburg,[2] Melvin attended Heritage High School and then went on to the University of Richmond[3] on a football scholarship, where he received a bachelor's degree in chemistry.

[4] Melvin's recreational interests include photography, piano, reading, music, cycling, tennis, and snowboarding.

[16] He reported to the Dallas Cowboys the following spring but pulled a hamstring a second time, officially ending his professional football career.

[14][17] Melvin began working in the Nondestructive Evaluation Sciences Branch at NASA's Langley Research Center in 1989.

He was assigned to the Astronaut Office Space Station Operations Branch, and the Education Department at NASA Headquarters in Washington, D.C. As co-manager of NASA's Educator Astronaut Program, Melvin traveled across the United States, discussing space exploration with teachers and students, and promoting science, technology, engineering and mathematics.

It took three spacewalks by crew members to prepare the Columbus Laboratory for its scientific work, and to replace an expended nitrogen tank on the Station's P-1 Truss.

STS-129 returned to Earth with them NASA Astronaut, Nicole Stott, following her tour of duty aboard the space station.

[2] Since retiring from NASA, Leland has given several STEM lectures of his experience in space to a wide range of audiences, as well as his football career in the NFL.

[21] He is featured in several National Geographic Space documentaries and videos,[22] including a 2010 episode of Dog Whisperer with Cesar Millan.

[23] In 2021, he featured in Season 2 of the Netflix television series Dogs, climbing Columbia Point with his Rhodesian Ridgebacks Roux and Zorro.