Skipet ble bygget i 1986 som «Niels Klim» for DSB sin rute mellom Århus og Kalundborg. «Niels Klim» kjørte parallelt på ruten med søsterskipet «Peder Paars» (nå MS «Color Viking»). Allerede i 1991 ble skipet kjøpt opp av Stena Line og ble på starten av Stena-karrieren brukt på flere ruter i England. Deretter ble fartøyet charteret til Lion Ferry under navnet «Lion King» for trafikk mellom Halmstad og Grenå. Stena Line tok tilbake skipet under eget navn og ble før nåtidens trafikk satt i trafikk i Spania, England og Polen. I 1997 ble «Stena Nautica» satt i trafikk igjen mellom Halmstad og Grenå. Siden 1999 har hun trafikkert ruten Varberg–Grenå.
I 2001 ble «Stena Nautica» modernisert og fikk et nytt bildekk ved Cityvarvet. Deler av skorstenen ble fjernet og sikkerhetssystemet oppgradert.
