Subfossil fecal pellets associated with Archaeolemur cf. edwardsi skeletal material from Anjohikely Cave in north-western Madagascar were probably derived from this large extinct lemur. Pellets were photographed, measured, and dissected. One of the pellets dates to 830 ± 60 years BP. Pellets contain a wide variety of items indicative of omnivory, including fibrous fruit exocarps and seeds; bat, rodent, frog, and lizard bone; gastropod shell; and crustacean and arthropod exoskeletons—all within a matrix of comminuted vegetation. Pollen contents from inside intact pellets support other paleoecological evidence that recent feeding had taken place in wooded grassland habitat. This diet is consistent with ethnohistorical data and anatomical studies that indicate hard-object feeding in Archaeolemur. Archaeolemur may have deliberately entered caves to forage, although caves would also have offered water, abundant shade, cool conditions, cryptic sleeping sites, and refuge from predators. Cave-exploring behavior is rare in primates, but consistent with anatomical evidence that Archaeolemur was well adapted for terrestrial locomotion as well as arboreal climbing.