Fruit traits that selectively deter vertebrate seed predators without affecting high-quality seed dispersers are said to exhibit directed deterrence. Directed deterrence has been criticized as being unlikely in natural systems, but has rarely been explicitly tested. We evaluated the potential for directed deterrence to explain the double-layered viscous fruit morphology and fruiting phenology of Terminalia impediens, a common canopy tree endemic to New Guinea. The large fleshy fruits of this tree are consumed and dispersed by cassowaries (Casuarius spp.) and are consumed and killed by palm cockatoos (Probosciger aterrimus). Fruit flesh in this tree species appears to function as a deterrent to seed predation by palm cockatoos; the fruits of T. impediens fall to the ground before ripening, and are avoided by palm cockatoos until after the flesh has rotted off the hard nut. We found that palm cockatoos are able to prey upon seeds from fruits without flesh on the forest floor more efficiently than they can consume seeds from unripe fruit still on the trees. Further, through foraging preference tests, we found that palm cockatoos largely ignore seeds within ripe fruit on the ground, but readily eat the seeds when the fruit flesh has been removed. Cassowaries consume the fruit whole, when ripe, and defecate seeds in piles away from parent trees, where seed predation rates are lower. These results challenge the prevailing view that fleshy fruits evolved in tight synchrony with high-quality seed dispersers and add support to the non-exclusive hypothesis that aspects of fruit fleshiness may also have evolved as a response to seed predation.