The most common representation of sea ice dynamics in climate models assumes that sea ice is a quasi-continuous non-normal fluid with a viscous-plastic rheology. This rheology leads to non-linear sea ice momentum equations that are notoriously difficult to solve. Recently a Jacobian-free Newton-Krylov (JFNK) solver was shown to solve the equations accurately at moderate costs. This solver is extended for massive parallel architectures and vector computers and implemented in a coupled sea ice-ocean general circulation model for climate studies. Numerical performance is discussed along with numerical difficulties in realistic applications with up to 1920 CPUs. The parallel JFNK-solver's scalability competes with traditional solvers although the collective communication overhead starts to show a little earlier. When accuracy of the solution is required (i.e. reduction of the residual norm of the momentum equations of more that one or two orders of magnitude) the JFNK-solver is unrivalled in efficiency. The new implementation opens up the opportunity to explore physical mechanisms in the context of large scale sea ice models and climate models and to clearly differentiate these physical effects from numerical artifacts. © 2013 Crown Copyright and Elsevier Inc.