In 1991 Gnanajothi conjectured: Each tree is odd-graceful. In this paper, we define the edge-ordered odd-graceful labeling of trees and show the odd-gracefulness of all symmetric trees.