Direct evidence of successful or failed predation is rare in the fossil record but essential for reconstructing extinct food webs. Here, we report the first evidence of a failed predation attempt by a pterosaur on a soft-bodied coleoid cephalopod. A perfectly preserved, fully grown soft-tissue specimen of the octobrachian coleoid Plesioteuthis subovata is associated with a tooth of the pterosaur Rhamphorhynchus muensteri from the Late Jurassic Solnhofen Archipelago. Examination under ultraviolet light reveals the pterosaur tooth is embedded in the now phosphatised cephalopod soft tissue, which makes a chance association highly improbable. According to its morphology, the tooth likely originates from the anterior to middle region of the upper or lower jaw of a large, osteologically mature individual. We propose the tooth became associated with the coleoid when the pterosaur attacked Plesioteuthis at or near the water surface. Thus, Rhamphorhynchus apparently fed on aquatic animals by grabbing prey whilst flying directly above, or floating upon (less likely), the water surface. It remains unclear whether the Plesioteuthis died from the pterosaur attack or survived for some time with the broken tooth lodged in its mantle. Sinking into oxygen depleted waters explains the exceptional soft tissue preservation.