Fyrirtækið var stofnað 1999 í tengslum við yfirlýsingu frá ríkisstjórn Íslands þess efnis að stefnt væri að nýtingu vetnis til samgangna (yfirlýsing frá 1998). Innlendir aðilar gerðust hluthafar í NýOrku í gegnum eignarhaldsfélagið VistOrku og þrír erlendir aðilar komu að stofnun fyrirtækisins, Daimler, Shell International & Norsk Hydro (síðar Statoil).
Marmið fyrirtækisins í byrjun var rannsóknar- og tilraunaverkefni tengd vetni. Árið 2001 var ECTOS verkefninu hleypt af stokkunum og sem hluti af því fóru þrír vetnisrafstrætisvagnar í umferð á vegum Strætó og byggð var fyrsta vetnisstöðin í heiminum sem aðgengileg var almenningi. Akstur vagnanna átti upphaflega að vera 2 ár en vegna jákvæðra niðurstaðna var ákveðið að framlengja verkefnið fyrst í gegnum ECTOS verkefnið sjálft en síðar í HyFLEET:CUTE verkefninu. Markmiðið var síðan að halda áfram með nýja kynslóð vagna í nýju verkefni en því þurfti að slá á frest vegna efnahagsaðstæðna síðari hluta árs 2008. Vagnarnir voru því í umferð í 4 ár.
Reynsla af notkun stöðvarinnar var mun betri en áætlanir gerðu ráð fyrir og því var ákveðið að tilraunakeyra einnig hefðbundna vetnisbíla. Á árinu 2007 var því SMART-H2 verkefnið sett af stað en markmiðið með því var að keyra minnst 20 vetnisbíla og gera tilraunaverkefni úti á sjó með vetni. Bílarnir urðu talsvert fleiri eða 35 þegar mest var frá hinum ýmsu framleiðendum, Daimler, Toyota, GM en flestir bílarnir komu frá Ford. Markmiðið var að tengja saman tilraunir og raðframleiðslu bíla en búist var við auknu framboði vetnisbíla eftir 2010. Bílaframleiðendur ákváðu hins vegar að fresta raðframleiðslu bíla til 2015 (sérstaklega vegna skorts á innviðum í heiminum). Það var því ákveðið að hætta akstri bílanna 2012 enda bílarnir orðnir gamlir (miðað við þróun) og erfitt að halda þeim við þar sem nýjar gerðir höfðu verið smiðaðar og hætt að framleiða varahluti í gömlu bílana. Einnig eru allir nýjir bílar með hærri geymsluþrýsting á vetni en sú stöð sem upphaflega var byggð á Skeljungsstöðinni við Grjótháls og því mikilvægt að uppfæra þá stöð. Stöðin var opnuð á ný árið 2018 sem hluti af Hydrogen Mobility Europe verkefninu sem styrkt er af Horizon 2020 rannsóknar- og nýsköpunaráætlun Evrópusambandsins.
Árið 2008 var sett vetnisraf ljósvél um borð í hvalaskoðunarskipið Eldingu. Verkefnið var einstakt þar sem markmiðið var að keyra ljósvél skipsins að hluta eða öllu leyti þar sem rafmagnið var framleitt með efnarafölum úr vetni. Verkefnið reyndist afar erfitt í framkvæmd en að lokum tókst að fá fullgilda vottun á skipið. Reynslan af þessu verkefni var einstök og þó að ekki tækist að keyra kerfið jafnmikið og lagt var upp með var þekkingarsöfnunin einstök og lærdómurinn hvernig hægt væri að taka næstu skref mikilvægur.
Á árabilinu 2008-2009 var mikil umræða innan fyrirtækisins um útvíkkun starfseminnar. Innlendir eigendur höfðu mikinn áhuga á að NýOrka tæki að sér rannsóknar og tækniverkefni tengd öðrum endurnýjanlegum orkberum t.d. rafgeymabílum, metan, lífdísel, o.s.frv. – raunverulega öllum þeim orkuberum sem hægt væri að framleiða úr innlendum hráefnum. Þessi stefnubreyting var síðan að fullu innleidd í fyrirtækinu stuttu síðar og síðan þá hefur fyrirtækið tekið þátt í verkefnum með rafgeymabíla, metanbíla, tengiltvinnbíla, lífdíselverkefni, o.s.frv. Einnig tók fyrirtækið að sér verkefnisstjórn Grænu Orkunnar sem er ráðgefandi fyrir ríkisstjórn Íslands varðandi orkuskipti í samgöngum.
Fyrirtækið býr því yfir einstakri þekkingu á vistvænum orkuberum og sinnir nú fyrst og fremst rannsóknar- og ráðgjafarverkefnum á því sviði. Ljóst er að orkuskipti í samgöngum munu taka talsverðan tíma (áratugi) en mikilvægt er að undirbúningur fyrir þau verði gerð með sem bestri þekkingu. Framtíðin er björt en ljóst er að enginn einn orkuberi mun leysa öll vandamálin og því líklegt að flóra orkubera fyrir samgöngur verði fjölbreyttari en verið hefur á síðustu öld. Vetni, rafgeymar, metan og lífdísill virðast vera þeir orkuberar sem líklegastir eru til að taka við af jarðefndaeldsneyti en bílaframleiðendur og markaðurinn munu hafa talsverð áhrif á hvaða orkuberar nái mestri útbreiðslu.