A methodology for the calculation of gradients with respect to design parameters in general Fluid-Structure Interaction problems is presented. It is based on fixed-point iterations on the adjoint variables of the coupled system using Algorithmic Differentiation. This removes the need for the construction of the analytic Jacobian for the coupled physical problem, which is the usual limitation for the computation of adjoints in most realistic applications. The formulation is shown to be amenable to partitioned solution methods for the adjoint equations. It also poses no restrictions to the nonlinear physics in either the fluid or structural field, other than the existence of a converged solution to the primal problem from which to compute the adjoints. We demonstrate the applicability of this procedure and the accuracy of the computed gradients on coupled problems involving viscous flows with geometrical and material non-linearities in the structural domain.