Im September 1983 wurden zwei baugleiche Fähren von Danske Statsbaner für die Route von Århus nach Kalundborg bei Nakskov Skibsværft in Nakskov bestellt. Die Schiffe wurden 1985 und 1986 als Peder Paars und Niels Klim abgeliefert, benannt nach einem Heldengedicht bzw. einer Romanfigur von Ludvig Holberg.
1987 wurden die Schiffe von Stena Line übernommen und in Stena Invicta und Stena Nautica umbenannt. Die Stena Nautica lag aber die meiste Zeit in Arhus auf. 1992 wurde sie von B & I Line gechartert und in der Irischen See als Isle Of Innisfree zwischen Pembroke Dock und Rosslare und später Holyhead und Dublin eingesetzt. 1995 kam sie zur Stena Line-Tochtergesellschaft Lion Ferry und wurde zwischen Halmstad und Grenå eingesetzt. Im April 1996 erfolgte die Umbenennung in Lion King II, ehe das Schiff im folgenden Monat von der Route Halmstad – Grenå abgezogen wurde. Im Mai 1996 wurde sie erneut in Stena Nautica umbenannt und kam unter der Flagge der Bermudas mit Heimathafen Hamilton in Fahrt. In der folgenden Zeit wurde die Stena Nautica verchartert und auf verschiedenen Routen im Stena Line-Netzwerk eingesetzt. Ab Februar 1999 bediente sie die Route Varberg – Grenå. Im Jahr 2002 wurde sie umgebaut. Das untere Passagierdeck wurde zu einem Fahrzeugdeck. Die Passagierkapazität wurde von 2000 auf 653 reduziert, während hingegen die Fahrzeugkapazität von 604 auf 1235 Meter erhöht wurde. Die Route Varberg – Grenå wurde im Januar 2020 eingestellt und das Schiff wechselte auf die Route Halmstad – Grenå.
Die Stena Nautica hat ein Schwesterschiff, die Color Viking.
