A distal tarsometatarsus and a fragment of carpometacarpus of a small galliform, the size of a recent quail, have been found in the late Early or early Middle Eocene of Chambi, in Tunisia. Although a large number of stem group representatives of Galliformes are known from the Eocene of the Northern Hemisphere, and one from the middle Eocene of Namibia, the taxon from Chambi differs from them and is described as a new genus and species. A very small zygodactyl form, represented by three distal tarsometatarsi, is also present in the same locality. This form, described as a new genus and species, is a stem group representative of the recent family Cuculidae. It shows a plesiomorphic morphology compared to the recent members of the Cuculidae, but it is, however, more derived than the younger genus Eocuculus. It is the earliest Cuculidae known so far.