Habitat degradation has caused a significant threat to wildlife, particularly to megafauna including the Asian elephant that has a large home range. Recolonization of Asian elephants in 1994 in and around Bardia National Park (BNP) has provided a unique study setting to address habitat change over two decades (1990–2013). Elephant presence data in 2013 was modeled using Ecological Niche Factor Analysis (ENFA), which identified the influential ecogeographical variables for elephant habitat. These variables were further used in a regression model to determine habitat suitability for 1990. We found that elephant suitable habitat has been lost between pre-recolonization (1990) and the year 2013 in and around BNP. Unsuitable elephant habitat increased overall by 22% in Bardia District and 20% inside BNP. Central to elephant habitat loss has been a large human population growth, re-forestation efforts with an increase in sal forests, and elephant alteration of vegetation by grazing. Available suitable habitat for elephants in and around BNP should be conserved and managed to prevent further degradation for the maintenance of the elephant population, which will help mitigate human-elephant conflict in the region.