This paper presents the implementation of an innovative solution based on heterogeneous autonomous vehicles to tackle maritime pollution (in particular, oil spills). This solution is based on native microbial consortia with bioremediation capacity, and the adaptation of air and surface autonomous vehicles for in situ release of autochthonous microorganisms (bioaugmentation) and nutrients (biostimulation). By doing so, these systems can be applied as the first line of the response to pollution incidents from several origins that may occur inside ports, around industrial and extraction facilities, or in the open sea during transport activities in a fast, efficient, and low-cost way. The paper describes the work done in the development of a team of autonomous vehicles able to carry as payload, native organisms to naturally degrade oil spills (avoiding the introduction of additional chemical or biological additives), and the development of a multi-robot framework for efficient oil spill mitigation. Field tests have been performed in Portugal and Spain’s harbors, with a simulated oil spill, and the coordinate oil spill task between the autonomous surface vehicle (ASV) ROAZ and the unmanned aerial vehicle (UAV) STORK has been validated.