Sabah, on the northeastern corner of Borneo, is concurrently Malaysia’s largest producer of oil palm (Elaeis guineensis) and home to the endangered Bornean elephants (Elephas maximus borneensis; elephants). Concomitantly, Sabah has been experiencing increasing and unsustainable human–elephant conflicts (HECs), which have not been thoroughly investigated from a human dimensions standpoint. To address this void, in March 2019, we conducted semi-structured interviews with 37 villagers located in the Sabah districts of Lahad Datu, Tawau, and Telupid to investigate villager cognitions regarding elephants, behaviors toward elephants, the formal and informal village institutions employed to mediate HECs, and the future viability of human–elephant coexistence. Respondents highlighted emotions of fear, anger, and frustration over crop and property damage that villagers were unable to effectively mitigate employing traditional institutions and strategies. Although negative emotions were somewhat tempered by the cultural significance of elephants, respondents indicated that coexistence with elephants remains challenging and is likely only viable under certain conditions: domestication of elephants, if elephants no longer destroyed crops, and/or if elephants were provided separate forested habitat away from humans. Our results demonstrated that elephant conservation in Sabah is viewed as a “not in my backyard” claim, which can hint at the presence of environmental injustice. We further examined Sabah HECs using an environmental justice framework and concluded that HEC as an environmental justice problem requires traditional fixes to be merged with more extensive, sustainable solutions that improve stakeholder agency.