Eucalyptus nandewarica was first formally described in 1990 by Lawrie Johnson and Ken Hill in the journal Telopea, from specimens collected in the Mount Kaputar National Park in 1986. The specific epithet (nandewarica) refers to the Nandewar Range where this species occurs.