In this paper, a Genetic Algorithm (GA) is used for solving underwater mission planning problem. The proposed genetic planner is capable of utilizing multiple Autonomous Underwater Vehicles (AUVs) and Remotely Operated Vehicles (ROVs) in a mission plan, as well as running multiple tasks in parallel on the agents level. The problem is described using STRIPS modeling language. The proposed planner shows high robustness regarding initial population set, which is randomly generated. Chromosomes have variable length, consisting of active and inactive genes. Various genetic operators are used in order to improve convergence of the algorithm. Although genetic planner presented in this work is for underwater missions, this planning approach is universal, and it is not domain dependent. Results for a realistic case study with five AUVs and almost 30 tasks show that this approach can be used successfully for solving complex mission planning problems.