In 1780 gaven Burgemeester en Gecommiteerde Vroedschappen toestemming tot het oprichten van een nieuwe molen. Een aantal coornwijnbranders richtte een compagnieschap op tot bouw en exploitatie van de molen, voor 26 ketels. Op 28 april 1781 legde Jan Bredero de eerste steen.
Op 14 december 1853 werd tijdens een hevige noordoosterstorm een roe afgeworpen; in de val vernielde deze een gedeelte van de balie. Eerder dat jaar was luijongen Johannes van der Klink uit één van de wieken gevallen, nadat iemand te vroeg de vang had gelicht; hij overleefde dit niet.
Tot 1894 werkten hier dagelijks negen personen om mout- en roggemeel te produceren voor de branderijen. Omstreeks 1895 werd het vennootschap Windkorenmolen De Palmboom ontbonden en de molen verkocht aan een 'gewone' graanmolenaar. Zo werd dit van een 'brandersmolen' een 'bakkersmolen'.
In 1899 werd Pieter Treurniet eigenaar. Twee jaar later beleefde deze, geheel buiten zijn schuld, een ramp: op 19 juli 1901 brak in de aan de overzijde van de Noordvest gelegen stoombranderij De Kraton brand uit. Als gevolg ontstond, door overslaande vonken, ook brand op De Palmboom en die bleek niet te blussen: de molen brandde uit.
Treurniet treurde evenwel niet maar verhuisde zijn bedrijf naar de naastgelegen Noordmolen; ondertussen verhuurde hij de peperbus van De Palmboom voor opslag. Hij besloot namelijk, de molen niet te herstellen: de romp werd tot halverwege de tweede zolder gesloopt en de overgebleven stomp voorzien van een dakje.
Rond 1955 werd J.J. Fontijne eigenaar. Deze bracht de tweede vloer omlaag zodat ruimte vrij kwam voor een extra zolder (die nog steeds aanwezig is). Hij gebruikte tot 1986 de molenstomp als garage voor zijn vrachtwagen en voor opslag van pompen. Daarna kocht de gemeente dit molenrestant aan.
Rond 1986 lagen al plannen klaar om deze molenstomp weer te completeren tot maalvaardige molen. Het werd een feit: op 6 mei 1987 gaf mr. Pieter van Vollenhoven, geboren Schiedammer, het startsein voor de herbouw.
Eerst werd de stomp voorzien van een nieuwe fundering en daarna begon men aan het metselwerk en daarvoor was tijd nodig: er moest een hoge stenen molen worden gereconstrueerd.
Op 26 september 1992 werden de roeden gestoken en op 14 mei 1993 volgde de officiële ingebruikname, wederom door Pieter van Vollenhoven.
In De Nieuwe Palmboom vestigde men het Nederlands Malend Korenmolenmuseum. Maar deze molen was niet alleen een museum: er werd ook gemalen, onder meer voor Branderij De Tweelingh die sinds 1986 Notaris moutwijnjenever vervaardigde uit mais-, rogge- en moutmeel.
Exploitant van het molengedeelte was Stichting Molen De Vrijheid, molenaar werd Leen Sprong die sinds 1989 bij die stichting in dienst was. De molen kreeg een breek- en een pletwals op de vierde zolder, zodat er diverse soorten granen geplet en gebroken konden worden voor het Echte Bakkersgilde.
In 1999 nam Niek Boekestein jr. (van de Aeolus in Vlaardingen) de bedrijfsleiding van diverse Schiedamse molens over. Dat leek veelbelovend voor de toekomst maar helaas: zijn plotselinge overlijden, op 12 juli 2000, betekende het voorlopige einde van alle maalactiviteiten.
Gedraaid werd er daarna nog veel: ook benoemde men een stadsmolenaar, die de molen zeer geregeld in bedrijf stelde. Later werd ook weer gemalen.
In het voorjaar van 2017 verdween de stenen romp in de steigers, om al het metsel- en voegwerk grondig na te lopen. Eind juni zag de molen er weer netjes uit.
Intussen was al besloten, de functie van museummolen van de Nieuwe Palmboom naar De Walvisch te verplaatsen. Deze zou daartoe in- en uitwendig grondig worden hersteld c.q. verbouwd.
Begin 2018 sloot het museum in De Nieuwe Palmboom. Bij deze gelegenheid kreeg de molen zijn vroegere naam terug, "De Palmboom", dus (het nieuwe was er inmiddels toch wel af).
Inmiddels is de derde etage verhuurd aan een accountantskantoor (Ham). Een andere etage is in gebruik als documentatiecentrum voor de molenstichting. Een andere vrijkomende etage zal vier dagen per week worden gebruikt voor de gin-academy en twee dagen voor molenwandelingen (kleine of grote toer).
In de loop van 2021 werd duidelijk dat beide roeden vervangen dienen te worden. In oktober dat jaar zette men beide roeden kaal. Eindmaart 2022 werden de nieuwe roeden gestoken.
