Mars Odyssey was originally a component of the Mars Surveyor 2001 program, and was named the Mars Surveyor 2001 Orbiter.
In August 2000, NASA solicited candidate names for the mission, which were evaluated by a naming committee consisting of Mark Dahl, Michael Meyer, Steve Saunders, and Don Savage.