We tested extended-spectrum beta-lactamase producing bacteria from wild gulls (Larus spp.) sampled in 2009 for the presence of mcr-1. We report the detection of mcr-1 and describe genome characteristics of four Escherichia coli and one Klebsiella pneumoniae isolate from Spain and Portugal that also exhibited colistin resistance. Results represent the earliest evidence for colistin-resistant bacteria in European wildlife.