Op 1 september 1717 velde een hevige storm de nog vrij nieuwe korenmolen op het bolwerk bij de Arkelpoort. De eigenaar ging er vervolgens toe over de eerste stenen korenmolen van Gorinchem te bouwen en hij mocht die plaatsen op De Kat, de aarden verhoging op Bastion I. Enige jaren eerder was op dat bastion een kat opgeworpen. Door de hoogte van die kat ving de molen minder wind dan voorheen het geval was geweest en bovendien waren de fundamenten van de molen door het gewicht van de aarden kat verzakt. De aldaar staande molen was dus eigenlijk een beltmolen.

In 1763 vroegen de bezitters van de molen toestemming om de kap tijdelijk van de molen te nemen, vervolgens de molen bijna 4 m. met steen hoger op te metselen en op een hoogte van ongeveer 6.50 m. een galerij aan te brengen. Wellicht speelde de begroeiing bij het Bastion de molenaar parten of maakte de bebouwing in de omgeving het nodig de molen te verhogen om een betere windvang te verkrijgen. Tot op de dag van vandaag is de afscheiding in het metselwerk als gevolg van de toen uitgevoerde verhoging te onderscheiden.

In 1825 kwam die molen voor 5/8 gedeelte in het bezit van Daniël Boxman, koopman te Gorinchem. Na zijn overlijden ging zijn aandeel in de molen over naar zijn zoon mr. Abraham Boxman. Deze persoon wist ook het resterende deel van de molen te verwerven, zodat hij hem in zijn geheel in handen kreeg, evenals de twee bijbehorende huizen in de Arkelstraat waarin ook een rosmolen was ondergebracht.
De rosmolen was al lang uit de tijd, maar toch speelde hij nog een rol in 1814. In januari van dat jaar, toen Gorinchem een belegerde vesting was, mochten de beide windkorenmolens slechts graan malen voor het ingesloten garnizoen. De burgerij was toen uitsluitend aangewezen op de Grote Rosmolen. Na de dood van mr. Abraham Boxman in 1856, nadat hij twee jaar eerder het ambt van burgemeester van zijn vaderstad om gezondheidsredenen had neergelegd, erfde zijn dochter Margaretha Alida Hendrika, de echtgenote van jhr. Frederik Gerrit Edmond Merkus van Gendt, de windkorenmolen en de inmiddels tot een dubbel woonhuis verbouwde huisjes in de Arkelstraat.
Al spoedig werden deze doorverkocht aan Hendrik Heijmans, die ze zes jaar later overdeed aan zijn broer Simon. Laatstgenoemde persoon en zijn twee dochters verkochten de molen in 1887 aan de molenaar Johannes Petrus de Visscher.

Bij de verkoop van de korenmolen op Bastion I in 1887 werd een merkwaardige bepaling vastgelegd: als binnen tien jaar de molen door het Rijk ten behoeve van openbare werken zou worden onteigend, zou de verkoper de helft krijgen van het onteigeningsbedrag dat de verkoopsom van ƒ 4000,-- te boven zou gaan. Toch zou dat een loze clausule blijken, want de molen is niet onteigend.

In 1889 brandde de molen uit, maar werd hersteld met onderdelen van de oliemolen Nooit Volmaakt, die toen al enige tijd buiten bedrijf was. Zo komt deze molen dus aan zijn naam. Zeer veel constructiedetails wijzen op een achtkante molen: zo is het boventafelement van deze ronde stenen molen achtkant uitgevoerd!
Na molenaar De Visscher kwam de molen in 1890 in het bezit van de koren- en schorsmolenaar Hendrik van den Bergh, die er ƒ 7000,-- voor betaalde. Deze woonde in Besoyen en liet het werk over aan een van zijn zonen. De grote concurrent - de stoommeelfabriek van Teunis van Andel gevestigd tussen de Havendijk en de Keizerstraat - was inmiddels door een brand voorgoed uitgeschakeld. De eigenaar van de nog altijd naamloze molen op Bastion I schafte in 1895 een gasmotor aan voor de aandrijving van de molenstenen, waardoor hij onafhankelijk van de weersomstandigheden kon werken.

In 1917 ging de molen in eigendom over op Bastiaan de Heus; deze verkocht hem tijdens de Tweede Wereldoorlog aan zijn zoon Pieter Marinus. In 1956 kocht de gemeente de molen voor ƒ 15.000,--. Eenvoudige herstelwerkzaamheden waren in 1942 uitgevoerd; in 1965 volgde een veel ingrijpender restauratie.

In 1992 nam het gemeentebestuur het besluit om beide walkorenmolens van de stad gelijktijdig maalvaardig te restaureren, wat in mei 1993 aanving. In augustus 1997 werd de molen op feestelijke wijze weer in bedrijf genomen door Z.K.H. Prins Claus.

Begin 2012 moest de molen enige tijd stilstaan, vooral vanwege een bouwvallig geworden stelling en noodzakelijke reparaties aan bovenwiel en enige balkkoppen.

In de loop van 2016 kwam de molen tot stilstand nadat twee molenaars hun werkzaamheden daar beëindigden. In februari 2017 pakten twee andere molenaars de draad op en op 25 februari was de molen voor het eerst in bijna een jaar draaiend te zien.
Begin september is één van de koppels stenen opnieuw afgesteld en er wordt sinds die tijd weer op vrijwillige basis  gemalen. Ook werd de molenwinkel in ere hersteld.

In maart 2022 begon men aan een restauratie die tot oktober zou duren: de romp geheel in de steigers om het metselwerk grondig te kunnen aanpakken, kapbedekking vernieuwd, kruiwerk gereviseerd, gangwerk nagelopen, diverse balkkoppen hersteld en tenslotte een hele schilderbeurt. Beide roeden zouden intussen worden nagekeken.

Op 5 september 2022 werden beide gerepareerde roeden weer gestoken en kreeg de molen twee nieuwe lange schoren. Het metselwerk is buiten en binnen grotendeels hersteld, zelfs heeft men hiertoe ten dele de fundering opengegraven.
In oktober was de Nooit Volmaakt in principe klaar, maar de molenaars hebben nog geruime tijd allerhande werk gehad aan schoonmaak en allerlei andere zaken. In februari 2023 maalde men hier voor het eerst in bijna een jaar weer.

Een technische bijzonderheid: de kruisarmen van het bovenwiel lopen aan de achterzijde tot in de vellingen door.
In de molen bevindt zich verder een ca. 200 jaar oude kaapstander, ooit gemaakt voor en door een Rijnlandse molenmaker.