Gustav W. Dahl var født i Trondheim i 1863, der han i første halvpart av 1890 årene hadde arbeidet som hotelltjener blant annet ved Grand Hotell cafe. At han ville prøve seg på hotelldrift i Kristiansund skyldtes nok mye hans kone som var fra Kristiansund, og gjennom henne var han blitt kjent med byen.
Dette ledet til at det i første halvpart av 1890-årene ble oppført et boligkompleks på tomten til den gamle Prestegården, med fasade mot Torvet og Bernstorffstedet. Det var stadskonduktør Hagbart Brinchmann som var byggherre og eier av bygget, hvor Grand Hotell etablerte seg.
Mai 1895 kunne man lese i en annonse i to av byens aviser at byens Grand Hotell åpner dørene 1. juni 1895, og annonsen var signert hotellets eier Gustav W. Dahl. Hotellet hadde 30 værelser, og foruten gjesterom hadde det udpakningsværelser, en elegant Salon, Læseværelse og Spisesal.
Driften av hotellet ser ut til å ha godt bra, for i 1897 etablerte Gustav W. Dahl seg som restauratør på Øvre Bakklandet i Trondheim. Dette kjøpet ble fulgt opp av et nytt kjøp våren 1900, da han også kjøpte Trondheims Grand Hotell.
Ettersom Gustav W. Dahl nå hadde satset så hardt i Trondheim ble det behov for en ny innehaver for Grand Hotell i Kristiansund. 20. november 1900 kunne man da også lese i avisen i Kristiansund at nye lederen for hotellet nå var Nils Nilsen.
Nils Nilsen var født i Sand i Ryfylke i 1869. Han hadde vært reisefører og tolk for den britiske godseier og vinkonge Fleetwood Sandeman og gjennom hans reiser gjennom flere europeiske land, hadde han fått et inngående kjennskap til hotelldrift. På det tidspunkt han tok over driften av hotellet var han faktor ved Sandemans gård Gulla i Surnadal. Trolig fikk Nils Nilsen også økonomisk støtte fra sin arbeidsgiver til å kjøpe hotellet. En av forandringene Nils Nilsen gjorde ved hotellet var å installere hustelefon på alle rom.
En av de større begivenhetene hotellet opplevde var å være vertskap for kongefamilien på dens kroningsferd den 18. juni 1906. Nils Nilsen sørget først for en bedre borgermiddag i gymnastikksalen og i andre rom ved Enggatens skole. Hans Majestet Kong Haakon VII overnattet senere på hotellet, mens Hennes Majestet Dronning Maud overnattet på kongeskipet Heimdal for å få mer ro neste morgen. Morgenen etter ble det arrangert en avskjedsfrokost for kongen, der medlemmer av formannskapet og embetsmenn med fruer deltok.
Så i 1899 døde Hagbart Brinchmann som eide bygningen der Grand Hotell holdt til, og hans enke, Laura Susanne Brinchmann (født Øwre) solgte da bygningen til Nils Nilsen våren 1907. Nils Nilsen var nå blitt eier av både hotellet og bygningen. Men så den 8. november 1907 brøt det ut brann i hotellets vedbu. Brannen ble oppdaget av nattevakten, og alarm ble slått. Mer enn 300 mann kom raskt til stede, samt 5 fra sjødampsprøyta, men det ble snart klart at det store trekomplekset ikke kunne reddes. To mennesker mistet livet i brannen. Disse var søstrene Anna og Augusta Sørensen som drev motehandel i første etasje av hotellet. Den flotte trebygningen i utført sveitserstil var nå blitt slukt av flammene.
Ikke lenge etter besluttet Nils Nilsen å bygge et nytt hotell på den samme tomten. Arkitekten ble Kristen Tobias Rivertz, og det nye hotellet som ble oppført i jugendstil, stod så ferdig januar 1909.