In Marconi et al. (2007), the theory of nonlinear Luenberger observers was exploited to prove that a solution to the asymptotic output regulation problem for minimum-phase normal forms always exists. The paper provided an existence result and a very general regulator structure, although unfortunately, no constructive method was given to design all the degrees of freedom of the regulator. In this paper, we complete this design by introducing an adaptive unit tuning the regulator online by employing system identification algorithms selecting the “best” parameters according to a certain optimization policy. Instead of focusing on a single identification scheme, we give general conditions under which an algorithm may be used in the framework, and we develop a particular least-squares identifier satisfying these requirements. Closed-loop stability results are given, and it is shown that the asymptotic regulation error is related to the prediction capabilities of the identifier evaluated along the ideal error-zeroing steady-state trajectories.