Feeding preference of fossil herbivorous mammals, concerning the coevolution of mammalian and floral ecosystems, has become of key research interest. In this paper, phytoliths in dental calculus from two gomphotheriid proboscideans of the middle Miocene Junggar Basin, Central Asia, have been identified, suggesting that Gomphotherium connexum was a mixed feeder, while the phytoliths from G. steinheimense indicates grazing preference. This is the earliest-known proboscidean with a predominantly grazing habit. These results are further confirmed by microwear and isotope analyses. Pollen record reveals an open steppic environment with few trees, indicating an early aridity phase in the Asian interior during the Mid-Miocene Climate Optimum, which might urge a diet remodeling of G. steinheimense. Morphological and cladistic analyses show that G. steinheimense comprises the sister taxon of tetralophodont gomphotheres, which were believed to be the general ancestral stock of derived “true elephantids”; whereas G. connexum represents a more conservative lineage in both feeding behavior and tooth morphology, which subsequently became completely extinct. Therefore, grazing by G. steinheimense may have acted as a behavior preadaptive for aridity, and allowing its lineage evolving new morphological features for surviving later in time. This study displays an interesting example of behavioral adaptation prior to morphological modification.