This study examined the feasibility of green hydrogen as a transport fuel for the very heavy vehicle (VHV) fleet in New Zealand. Green hydrogen is assumed to be produced through water electrolysis using purely renewable energy (RE) as an electricity source. This study chose very heavy vehicles as a potential market for green hydrogen, because it is considered “low-hanging fruit” for hydrogen fuel in a sector where battery electrification is less feasible. The study assumed a large-scale, decentralized, embedded (dedicated) grid-connected hydrogen system of production using polymer electrolytic membrane (PEM) electrolysers. The analysis comprised three steps. First, the hydrogen demand was calculated. Second, the additional RE requirement was determined and compared with consented, but unbuilt, capacity. Finally, the hydrogen production cost was calculated using the concept of levelized cost. Sensitivity analysis and cost reduction scenarios were also undertaken. The results indicate an overall green hydrogen demand for VHVs of 71 million kg, or 8.5 PJ, per year, compared to the 14.7 PJ of diesel fuel demand for the same VHV travelled kilometres. The results also indicate that the estimated 9824 GWh of RE electricity that could be generated from consented, yet unbuilt, RE projects is greater than the electricity demand for green hydrogen production, which was calculated to be 4492 GWh. The calculated levelized hydrogen cost is NZD 6.83/kg. Electricity cost was found to be the most significant cost parameter for green hydrogen production. A combined cost reduction for CAPEX and electricity translates to a hydrogen cost reduction in 10 to 20 years.