Abstract The problem of coverage is common to many domains. Application areas range from smaller scales operations such as vacuum cleaning, lawn mowing, and painting, to large scale ones such as search and rescue, environmental monitoring, and automated farming. Of particular interest is the problem of complete area coverage which ensures all regions are visited. In large scale coverage operations, single robot approaches take too long, thus multi-robot approaches are preferable. Furthermore, several real world vehicles are nonholonomic, but can be modeled using Dubins vehicle kinematics. This paper focuses on environmental monitoring of aquatic environments using Autonomous Surface Vehicles (ASVs). In particular, we propose a novel approach for solving the problem of complete coverage of a known environment by a multi-robot team consisting of Dubins vehicles. It is worth noting that both multi-robot coverage and Dubins vehicle coverage are NP-complete problems. As such, two heuristics that efficiently solve the problem are discussed. The proposed methods are tested both in simulations to measure how they scale up and with a team of ASVs operating on a large lake.