Mixed-species assemblages are common in nature, providing mutual benefits to associating species including anti-predator advantages or resource facilitation. However, associating with other species may also impose costs through kleptoparasitism (food theft). Identification of these costs, and how they vary when different species breed alongside one another, is essential to understand the payoffs of mixed-species assemblages. We explore the costs of kleptoparasitism for greater crested terns Thalasseus bergii provisioning offspring at a single-species colony, where individuals suffer kleptoparasitism from conspecifics, and at a mixed colony where terns breed alongside Hartlaub’s gulls Chroicocephalus hartlaubii and are vulnerable to both intra- and interspecific kleptoparasitism. Gull presence increased both kleptoparasitic attacks and the proportion of prey lost or stolen during provisioning, relative to the single-species colony. Provisioning adults suffered additional energetic costs in response to gull kleptoparasitism, requiring more attempts to deliver prey, taking longer to do so, and swallowing more prey (to the detriment of their offspring). Gulls also increased the duration of tern vulnerability to kleptoparasitism, because they continued to steal food from adults and chicks after precocial chicks left the nest, when intraspecific kleptoparasitism is negligible. Terns breeding in a mixed colony therefore suffer direct and indirect costs through decreased provisioning and increased provisioning effort, which may ultimately impact reproductive success, resulting in colony decline where kleptoparasitism is frequent. This study illustrates how forming a mixed-species seabird breeding assemblage has costs as well as benefits, potentially fluctuating between a parasitic and a mutualistic relationship.