This paper studies the distributed optimal output agreement problem for multi-agent systems described by uncertain nonlinear models. By using partial information of an objective function, the design aims to steer the outputs of the agents to an agreement on the optimal solution to the objective function. To solve this problem, this paper introduces distributed coordinators to calculate the ideal outputs, and designs reference-tracking controllers for the agents to follow the ideal outputs. To deal with the nonlinear uncertain dynamics, the closed-loop multi-agent system is considered as a dynamical network, and Sontag's input-to-state stability (ISS) properties are employed to characterize the interconnections. It is shown that output agreement in multi-agent nonlinear systems is achievable by means of distributed optimal coordinators via a small-gain approach. Numerical simulations are employed to show the effectiveness of the design.