This paper describes a new class of autonomous marine vehicles named Medusa and highlights their role in a number of EU projects addressing multiple vehicle scenarios. The MEDUSA vehicles, with surface and diving versions, were designed and built at the Institute for Systems and Robotics, IST, Univ. de Lisboa, Portugal as a result of an effort aimed at affording researchers and practitioners of marine robotics tools to: i) assess the efficacy of cooperative motion control and navigation algorithms and ii) seamlessly execute scientific and commercial missions with multiple robots at sea. We first define the problem of designing the MEDUSA-class of vehicles by describing the desired functional requirements that motivated their development and then present our solution. Mechanical and electrical design considerations that relate to the requirements are explained, and the software architecture is described. This includes a brief overview of the navigation system, the main lower-level control loops which other features can build upon, and some of the higher-level algorithms for multiple-vehicle cooperative missions. We also illustrate the functionality of the mission control system, a dedicated software suite that allows operators to seamlessly program and follow the state of execution of cooperative missions involving multiple vehicles, possibly running different operations or missions in parallel. Finally, we summarize the participation of IST and the MEDUSA vehicles in a number of representative EC-funded Marine Robotics-related projects.