In this work, we propose both a theoretical framework and a numerical method to tackle shape optimization problems related with fluid dynamics applications in presence of fluid-structure interactions. We present a general framework relying on the solution to a suitable adjoint problem and the characterization of the shape gradient of the cost functional to be minimized. We show how to derive a system of (first-order) optimality conditions combining several tools from shape analysis and how to exploit them in order to set a numerical iterative procedure to approximate the optimal solution. We also show how to deal efficiently with shape deformations (resulting from both the fluid-structure interaction and the optimization process). As benchmark case, we consider an unsteady Stokes flow in an elastic channel with compliant walls, whose motion under the effect of the flow is described through a linear Koiter shell model. Potential applications are related e.g. to design of cardiovascular prostheses in physiological flows or design of components in aerodynamics.