This paper proposes a novel approach to derive analytical behavioral models of Lithium batteries, based on a Genetic Programming Algorithm (GPA). This approach is used to analytically relate the battery voltage to its State-of-Charge (SoC) and Charge/discharge rate (C-rate), during a battery discharge phase. The GPA generates optimal candidate analytical models, where the preferred one is selected by evaluating suitable metrics and imposing a sound trade-off between simplicity and accuracy. The GPA proposed model can be seen as a generalization of the equivalent circuit models currently used for batteries, with the possible advantage to overcome some inherent limits, like the extensive laboratory characterization for model parameters evaluation. The presented case-study refers to a Lithium Titanate Oxide battery, with SoC values going from 5 to 95%, at C-rate values between 0.25C and 4.0C.