Eucalyptus gillenii was first formally described in 1926 by Alfred Ewart and Lesley Kerr in the Proceedings of the Royal Society of Victoria from samples collected near Mount Gillen by Ewatt in 1924. It is named for Francis James Gillen who was an anthropologist, ethnologist and the first postmaster at Alice Springs. Mount Gillen in the MacDonnell Ranges, where the type specimen was collected from, was also named for the same man.