Die Bergen Line bestellte die „Nordstjernen“ als dringenden Ersatz für das ehemalige Flaggschiff des Unternehmens, das ebenfalls „Nordstjernen“ hieß, 1937 gebaut wurde und im September 1954 nach einer Havarie im Raftsundet verloren ging. Der Auftrag für ein neues Passagier-, Post- und Frachtschiff wurde an die Werft Blohm & Voss in Hamburg vergeben, die sich erst kürzlich von den schweren Kriegsschäden durch Luftangriffe in den letzten Monaten des Zweiten Weltkriegs erholt hatte. Die Beschränkungen für den Schiffbau in Deutschland wurden erst 1953 aufgehoben, und die Werft war bestrebt, internationale Aufträge zu gewinnen und ihren Ruf wieder aufzubauen. Sie konnten eine schnelle Lieferung im Frühjahr 1956 garantieren, was den Anforderungen der Bergen Line sehr entgegenkam. Der Vertrag wurde im Dezember 1954 unterzeichnet, und die Bauarbeiten am Rumpf mit der Baunummer 787 begannen sofort. Es kam zu einigen Verzögerungen aufgrund von Materialmangel, sodass der Kiel erst im Sommer 1955 gelegt werden konnte. Danach ging der Bau zügig voran, und das Schiff wurde am 26. Oktober 1955 in die Elbe zu Wasser gelassen. Der Innenausbau verlief reibungslos, und am 24. Februar 1956 – einige Tage früher als geplant – wurde die neue „Nordstjernen“ an die Bergen Line ausgeliefert. Sie hatte eine Bruttoraumzahl von 2194, eine Länge von 80,77 Metern, eine Breite von 12,6 Metern und einen Tiefgang von 4,5 Metern. Die „Nordstjernen“ bot Platz für 450 Passagiere, davon konnten 195 in den Kabinen der ersten und zweiten Klasse untergebracht werden. Zusätzlich konnten bis zu 645 Tonnen Fracht in den beiden vorderen Frachträumen transportiert werden. Angetrieben wurde das Schiff von einem einzigen 3000 PS starken 6-Zylinder-Zweitakt-Dieselmotor von Burmeister & Wain mit Verstellpropeller, der eine Höchstgeschwindigkeit von 15,5 Knoten ermöglichte. Der Innenausbau des Schiffs war einfach gehalten. Alle öffentlichen Räume befanden sich auf einem Deck – der erste-Klasse-Bereich vorne mit einem komfortablen Salon, dem Eingangsbereich und dem Speisesaal, sowie der zweite-Klasse-Bereich hinten mit Cafeteria und einem weiteren Salon. Die Ausstattung war von besonders hohem Standard und wurde vom berühmten norwegischen Künstler Paul René Gauguin gestaltet. Fast alle Kunstwerke sind noch erhalten und können bis heute bewundert werden.

Die „Nordstjernen“ trat am 1. März 1956 in den Hurtigruten-Dienst ein und wurde schnell ein beliebtes und erfolgreiches Mitglied der Flotte. Im Jahr 1968 kamen neue Herausforderungen hinzu. Zusätzlich zu den regulären Hurtigruten-Fahrten führten die Reedereien eine neue Svalbard-Express-Verbindung nach Spitzbergen ein. Alle beteiligten Unternehmen stellten ihre jeweiligen Flaggschiffe, und für die Bergen Line übernahm die „Nordstjernen“ diese Rolle. Diese Route wurde zu einem attraktiven Angebot für den Tourismus und wurde jeden Sommer bis 1982 durchgeführt. Von 1976 bis 1979 wurden Frühlingskreuzfahrten zu den Shetlandinseln ins Programm der „Nordstjernen“ aufgenommen. Im Januar 1979 kündigte die Bergen Line nach 85 Jahren ihren Rückzug aus dem Hurtigruten-Dienst an. Ihr Anteil an der Hurtigruten-Betreibung, einschließlich vier eingesetzter Schiffe, wurde an die nordnorwegische Reederei Troms Fylkes Dampskipsselskap verkauft. Die „Nordstjernen“ erhielt die Hausfarben des neuen Eigentümers und der Heimathafen wurde nach Tromsø verlegt. Ansonsten änderte sich wenig, und die „Nordstjernen“ fuhr weiterhin im Hurtigruten-Dienst. Anfang der 1980er-Jahre kamen neue, deutlich größere Schiffe mit Ro/Ro-Ladeeinrichtungen in den Hurtigruten-Einsatz. Die klassischen Schiffe der 1950er- und 60er-Jahre begannen veraltet zu wirken. Einige ältere Schiffe wurden bereits außer Dienst gestellt und durch Neubauten ersetzt. Die „Nordstjernen“ blieb im Dienst, es wurde jedoch beschlossen, sie umfassend zu modernisieren. Diese Arbeiten wurden im Winter 1982–83 bei Mjellem & Karlsen in Bergen durchgeführt. Der alte Hauptmotor wurde durch einen neuen 3600-PS-Dieselmotor vom Typ MaK mit 8 Zylindern und 4 Takten ersetzt. Gleichzeitig wurde der Innenraum vollständig renoviert, und die Aufteilung in erste und zweite Klasse wurde abgeschafft. Viele ehemalige Erste-Klasse-Kabinen wurden umgebaut und mit privaten Dusche/WC ausgestattet. Dadurch reduzierte sich die Kabinenkapazität auf 179 Passagiere. Am 23. März 1983 begann die modernisierte „Nordstjernen“ ihre erste neue Hurtigruten-Reise. Die Umbaumaßnahmen galten als voller Erfolg, und der neue, stärkere Motor ermöglichte eine Höchstgeschwindigkeit von fast 19 Knoten. In den Folgejahren blieb sie ein beliebtes Schiff. Im August 1984 wurde an Bord die erste Hochzeit gefeiert. Ein prägendes Ereignis war der Neujahrssturm in den frühen Morgenstunden des 1. Januar 1992: Die „Nordstjernen“ befand sich auf Südkurs bei Ålesund und bereitete sich auf eine stürmische Überfahrt nach Måløy vor. Der Wind steigerte sich jedoch zu Orkanstärke, und das Schiff musste mehrere Stunden auf See bleiben, fern der Küste, unter äußerst schwierigen Bedingungen manövrierend. Die erschöpfte Besatzung erreichte Måløy mit mehrstündiger Verspätung. Inzwischen war klar, dass die letzten Hurtigruten-Schiffe der 1950er- und 60er-Jahre in die Jahre gekommen waren. Die Reedereien planten eine neue Generation großer, kreuzfahrtähnlicher Schiffe zur Ablösung der klassischen Postschiffe. Die ersten neuen Schiffe wurden 1993 in Dienst gestellt, und nach und nach wurden die alten Schiffe ausgemustert. Der Ersatz für die „Nordstjernen“ war die neue „Nordlys“, die 1994 in Dienst ging. Viele rechneten mit dem endgültigen Ende der „Nordstjernen“ als Hurtigruten-Schiff. Doch es kam anders: Einige Verantwortliche bei Troms Fylkes hielten es für verfrüht, sie außer Dienst zu stellen, da sie einen relativ neuen Hauptmotor und einen modernisierten Innenraum hatte. In Anlehnung an die erfolgreichen Svalbard-Express-Fahrten der 1970er-Jahre beschlossen sie, die „Nordstjernen“ im Sommer für Spitzbergen-Reisen von Tromsø aus einzusetzen und im Winter als Ersatzschiff auf der Hurtigruten zu nutzen. So begann sie im Sommer 1994 mit einwöchigen Spitzbergen-Kreuzfahrten, die ein großer Erfolg wurden und bis 2009 mit Variationen wiederholt wurden. In den folgenden Jahren kehrte die „Nordstjernen“ häufig in den Hurtigruten-Dienst zurück, vor allem im Winter oder als Ersatz für andere aus der Flotte ausgeschiedene Schiffe. Zwischen dem Winterdienst und den Sommerfahrten nach Spitzbergen wurden gelegentlich zusätzliche Kreuzfahrten durchgeführt. Im Jahr 2003 kehrte sie für eine Reise nach Hamburg zurück, wo sie gebaut worden war, und erneut zu ihrem 50. Geburtstag im Jahr 2006. Kurz darauf wechselte sie zum zweiten Mal ihre Schornsteinfarben, als die letzten beiden Hurtigruten-Gesellschaften zu Hurtigruten ASA fusionierten und die gesamte Flotte ein neues Corporate Design erhielt. Doch auch die längste Karriere geht einmal zu Ende. Im Jahr 2012 wurde die „Nordstjernen“ schließlich überflüssig. Ihre letzte Hurtigruten-Fahrt fand im März 2012 statt, gefolgt von einer letzten Spitzbergen-Saison im Sommer. Die letzte Reise war die Rücküberführung von Spitzbergen nach Bergen im August, wo sie am 1. September 2012 in ihren ehemaligen Heimathafen einlief.