Abstract: A new partitioned algorithm is described for solving fluid-structure interaction (FSI) problems coupling incompressible flows with elastic structures undergoing finite deformations. The new algorithm, referred to as the Added-Mass Partitioned (AMP) scheme,  overcomes the added-mass instability that has for decades plagued partitioned FSI simulations of incompressible flows coupled to light structures.  Within a Finite-Difference framework, the AMP scheme achieves fully second-order accuracy and remains stable, without sub-time-step iterations, even for very light structures when added-mass effects are strong. The stability and accuracy of the AMP scheme is validated through mode analysis and numerical experiments. Aiming to extend the AMP scheme to an Finite-Element framework, we also develop an accurate and efficient Finite-Element Method for solving the Incompressible Navier-Stokes Equations with high-order accuracy up-to the boundary.