Mølsted war der Sohn des Schiffsbauers und Fischers Andreas Adolf Nikolaj Mølsted (1839–1893) und dessen Frau Ane Hans-Nielsdatter (1830–1905). Seine erste Ausbildung erhielt er 1879 in Kopenhagen an der Schule der technischen Gesellschaft (Det tekniske Selskabs Skole). Im selben Jahr machte er eine Seereise auf der FregatteJylland nach England, Madeira und Russland (St. Petersburg). Nach der Rückkehr begann er 1880 ein Studium an der Königlich Dänischen Kunstakademie in Kopenhagen, das er 1885 mit dem Diplom abschloss. Seine Lehrer waren u. a. Frederik Vermehren, Jørgen Roed, Julius Exner, Niels Simonsen und Carl Bloch. Studienreisen führten ihn während dieser Zeit 1880 nach Paris und 1882 nach London.
Mølsted stellte 1884 auf der Dezemberausstellung im Schloss Charlottenborg zum ersten Mal aus und war dort danach regelmäßig auf den Frühjahrsausstellungen mit seinen Werken vertreten. Mølsted malte Motive der Küste um Kopenhagen und Jütland, teils mit Seeleuten und Fischern als Staffage versehen. Ebenso malte er große Schlachtenbilder historischen Inhalts sowie im Alter auch Genrebilder. Er war Vorstandsmitglied des Künstlerverbandes seit 1904.
Mølsted war seit dem 20. Oktober 1891 mit Ingine Dorothea (Thea) Svendsen (1862–1948) verheiratet, das Paar hatte drei Töchter. Mølsted starb 1930 in seiner Heimatstadt, er wurde auf dem Dragør Kirkegård bestattet.[1]
1974 wurde das Atelier des Malers in seiner Heimatstadt Dragør als Museum eröffnet, es ist Teil des Museum Amager und zeigt eine Auswahl seiner Kunstwerke.[2]