Description: In climate reanalyses for multi-decadal or longer scales with coupled atmosphere-ocean General Circulation models (CGCMs) it can be assumed that the growth of prediction errors arises chiefly from imprecisely known model parameters, which have a nonlinear relationship with the climate observations (paleoclimate proxies). Also, high-resolution CGCMs for climate analysis are extremely expensive to run, which constrains the applicability of assimilation schemes. In a model framework where we assume that model dynamic parameters account for (nearly) all forecast errors at observation times, we compare two computationally efficient iterative schemes for approximate nonlinear model parameter estimation and joint flux estimation (taking the specific shape of freshwater from melting in the Greenland ice sheet), and its physically consistent state. First, a trivial adaptation of the strong constraint incremental 4D-Var formulation leads to what we refer to as the parameter space iterative extended Kalman smoother (pIKS); a Gauss-Newton scheme. Second, a so-called parameter space fractional Kalman smoother (pFKS) is an alternative controlled-step line search, which can potentially be a more stable approach. While these iterative schemes have been used in data assimilation, we revisit them together within the context of parameter estimation in climate reanalysis, as compared to the more general 4D-Var formulation. Then, the two schemes are evaluated in numerical experiments with a simple 1D energy balance model (Ebm1D) and with a fully-coupled Community Earth System Model (CESM v1.2). Firstly, with Ebm1D the pFKS obtains a cost function similar to the adjoint method with highly reduced computational cost, while an ensemble transform Kalman filter with an m = 60 ensemble size (ETKF60) behaves slightly worse. The pIKS behaves worse than the ETKF60, but an ETKF10 (m = 10) is even worst. Accordingly, with CESM we evaluate the pKFS and the ETKF60 along with an ETKF with Gaussian Anamorphosis (ETKF-GA60). From all the options, the pFKS has the lowest cost function and seems the favored overall option under heavy computational restrictions, but the ETKF obtains better estimates of the flux term.