Créé en 1992 par Aldo Grimaldi, la compagnie était à l'époque une filiale du groupe Grimaldi. Elle popularisait le concept du cruise-ferry en Italie avec des navires de grande capacité et de grand confort.
En 2008, les inscriptions "Grimaldi Lines" que les navires portaient sont remplacés par le nom "Grandi Navi Veloci" puis en 2016 par un nouveau logo démesuré était arboré. En octobre 2010, le groupe Mediterranean Shipping Company (MSC) prenait 50% du capital de GNV et devenait son propriétaire en 2011. En 2020, GNV exploitait treize navires en Méditerranée sur quinze lignes. En avril 2021, GNV attendait un ferry neuf, le "GNV Bridge" ainsi que deux ferries (les "Pride of Bruges" et "Pride of York") rachetés à la compagnie anglaise P&O.
GNV, qui veut consolider sa présence sur le marché international, décidait en octobre 2021 de renforcer son service entre le port français de Sète et le Maroc pour 2022 en disposant un cinquième navire, soit un navire supplémentaire, pour des liaisons Sète-Tanger ou Sète-Nador. Dont les rotations concernaient aussi le port de Gênes, tête de ligne et celui de Barcelone pour des escales intermédiaires. GNV espérait ainsi disposer d'un réseau complet vers les principaux ports de la Méditerranée. GNV opère aussi une liaison journalière vers l'Albanie, avec Bari-Duraz.
En janvier 2022, GNV passait commande auprès du constructeur chinois Guangzhou Shipyard International de quatre grands navires livrables à partir de la fin 2024. D'une longueur de 218 mètres, ces ferries disposeront de 303 cabines à bord pour une capacité de 1 500 passagers et 3 100 mètres linéaires de pont garage. Avec ses 19 grands ferries de 160 à 214 mètres de long, Grandi Navi Veloci est la marque phare dans le secteur des ferries de MSC, qui regroupe aussi les compagnies SNAV et Caremar.
Vendu par l'armement français Brittany Ferries à GNV en février 2022, le "Cap Finistère" rejoignait la Méditerranée et le chantier naval Nuova Meccanica Navale de Naples où il était mis aux couleurs et aux standards de GNV. Il changeait également de nom et devenait le "GNV Spirit". Il devenait ainsi le vingt-cinquième navire de la compagnie.
Le samedi 14 janvier 2023, le "La Superba" de GNV était victime d'un incendie alors qu'il se trouvait à quai, au port de Palerme. Le navire qui assure la liaison entre Palerme et Naples était arrivé la veille dans le port sicilien. Le feu s'est déclaré dans le pont-garage et les 180 passagers présents à bord ont pu être facilement évacués. Le navire était gravement endommagé, les dégâts étaient importants à bord du ferry long de 211,50 mètres déjà victime d'un incendie en salle des machines en 2009, alors qu'il se trouvait dans le port de Gênes.
Le 25 décembre 2023, le premier des quatre ferries commandés par GNV en 2022 était lancé en Chine. Il portait le nom de "GNV Polaris". C'était la première fois que GNV faisait construire ses navires en Chine.
Début mars 2024, les ferries "Sharden" et "Moby Vinci" de Moby Line passaient sous la bannière de GNV. Ils étaient rebaptisés "GNV Sirio" et "GNV Auriga". La flotte GNV s'élevait à 28 navires desservant 31 lignes dans 7 pays différents à ce moment-là.
Début juin 2024, GNV déclarait la "perte totale constructive" du ferry "La Superba". Resté inutilisé et non réparé dans le port de Palerme depuis l'incendie de janvier 2023, la coque du navire abandonné devait terminer son dernier voyage dans l'un des sites de démolition en Turquie.
Le 23 octobre 2024, GNV prenait livraison du "GNV Polaris" qui devait entrer en service en janvier 2025. Dans le même temps, GNV se séparait du "GNV Aries" qui était destiné à un chantier de déconstruction en Turquie. C'était l'ancien "Pride of York" de P&O Ferries entré en flotte GNV au printemps 2021.