Merthyr och Rhymney AM kommer att avgå före årets val efter 17 år i Cardiff Bay.
Han talade om BBC Radio Wales söndagstilläggsprogram och sade att många politiker, däribland några i hans eget parti, var nervösa och skeptiska till decentralisering 1999.
Men den uppfattningen är nu "långt borta".
Samtidigt som han var "en mycket tidig konverterare", sade han att det nära resultatet av folkomröstningen - 50,3 % röstade för och 49,7 % röstade emot inrättandet av församlingen - skapade "en hel del nervositet".
Han sa: "Min åsikt var alltid beviset på puddingen är i ätandet, det handlar om vad institutionen gör - i termer av social förändring - som verkligen betyder något."
Lewis ansåg med eftertryck att decentraliseringen skulle kunna användas för att ta itu med områden där Wales har en särskild nackdel för England, inklusive hälsa, utbildning och fattigdomsbekämpning.
Den tidigare kemiläraren beskrev att ta på sig utbildningsportföljen som "en dröm besannas" och sade att reformer av läroplanen och lärarutbildningen var två av hans stoltaste prestationer.
Han sade: "Det gamla skolprogrammet i England och Wales finns inte längre.
"Wales har nu sin egen säregna väg och egen säregna framtid när det gäller hur våra skolor kommer att se ut."
Han sade att de reformer som sker här bygger på "verkliga bevis" och inte "ideologiskt drivna", vilket är vad han fruktar händer i England med "marknadsföring av utbildning".
Genom att införa en skandinavisk modell - som inkluderar barn som lär sig genom lek - hoppas han att lärarna kommer att bli bättre kvalificerade och att normerna kommer att stiga.
"Vi efterliknar inte England, vi efterliknar de bästa", sade Mr Lewis.
Detta trots ett antagande han tror är gjort av många att Wales bör se England som en "guld standard" och om något annat prövas här, är det på något sätt misstänkt och andra klass.
"Jag hoppas, att som devolution har mognat genom åren, vi äntligen börjar bryta sig loss från den typen av mentalitet," tillade han.
"Vi är fullt kapabla att sätta upp vår egen agenda och följa den och basera den, i globala termer, på hur det bästa ser ut.
"Det är den verkliga utdelningen från devolutionen. Det borde alltid vara där vi tänker."
Wales har "brutit sig" från England och är nu kapabel att sätta sin egen agenda tack vare devolution, har avgående utbildningsminister Huw Lewis sagt.