We report a tarsometatarsus and an associated pedal phalanx from the lower Eocene London Clay of Walton-on-the- Naze (Essex, UK). The specimen resembles the tarsometatarsus of the taxon Limnofregata (Fregatidae), but it belongs to a species that is distinctly larger than any other, extinct or extant, frigatebird, from which it also differs in some morphological features. Because of a close stratigraphical and geographical provenance, as well as a similar large size and frigatebird-like morphology, we consider it possible that the fossil belongs to Marinavis longirostris. This large seabird was initially described from the London Clay of Abbey Wood and is based on fragments of the rostrum, which likewise show a resemblance to the Fregatidae. If correctly assigned to the Fregatidae, the fossils would be among the earliest records of frigatebirds and the first fossils of this group of birds from the Paleogene of Europe, but we note that our tentative classification is still afflicted with considerable uncertainty.