Ecosystem services (ES), or tangible and intangible goods and services from nature, are an integral part of the rural economy in Nepal. However, there is limited recognition of their contribution to human wellbeing. To understand the linkages between local people and ES, an integrated assessment based on the Millennium Ecosystem Assessment framework was undertaken in Rautamai Rural Municipality of Udayapur District, Eastern Nepal. The study applied three broad approaches and multiple tools. This included a set of participatory tools (10 focus group discussions and 36 key informant interviews), followed by a household survey (439 households), and complemented by geospatial tools. The study identified three major ecosystems, namely forest ecosystems, agro-ecosystems, and freshwater ecosystems on which over 75% households were dependent for their livelihood. Collectively, these ecosystems provide 27 provisioning services, 14 regulating, 6 cultural, and 4 supporting services. Among the three ecosystems, the forest ecosystem provides the maximum number of services (40%). However, about 69% households depend on agro-ecosystems as their primary source of livelihoods. There have been subtle changes in land use over the last 18 years, which has had notable impacts on the flow of ecosystem services, and it reflected in people's perceptions. The study highlights the importance of ecosystem services and the implications of land use change on the flow of these services and wellbeing of people in rural Nepal. The findings of this study will be instrumental for land use planning and incentive-based conservation being planned by Nepal aimed at building socio-ecological resilience.