In arid regions, an oasis plays an important role. It is nearly the only support of living and economic development for the local people. In recent years, the recession of the oasis areas appeared to be significant in Northwest China. It caused a series of environmental problems and part of the area even became the source of sandstorms. In this article, the long-term vegetation change of the Ejina Oasis, which is located in the downstream area of the Heihe River basin, was analyzed based on remote sensing data. The quantitative relationship between the runoff of the Heihe River and the vegetation change of the Ejina Oasis from 1989 to 2006 was established using Advanced Very High Resolution Radiometer (AVHRR) time-series. The vegetation growth of the Ejina Oasis depends on the runoff of the Heihe River. The time lag of the impact of the runoff on the vegetation of the Ejina Oasis is 1 year. The smallest water amount that can sustain the demand of the eco-environment of the Ejina area was estimated. The result can serve as a reference for decision-making processes at the government level, finally allowing for a better allocation of water resources in the Heihe River basin.