In this work a new class of methods for upscaling Fluid-Structure Interaction (FSI) problems from the pore-level to a macroscale is proposed. A fully coupled FSI problem for Stokes fluid and an elastic solid is considered at the pore-level. The solid, due to coupling with the fluid, material nonlinearities, and macroscopic boundary conditions, can deform enough so that the pore-space is altered significantly. As a result, macroscopic properties such as the permeability of the porous media become nonlinearly dependent on the fine-scale displacements. Therefore, classical upscaled models, such as Biot's equations, can no longer be applied. We propose a series of numerical upscaling models in the context of the Multiscale Finite Element Method (MsFEM) which couple this fine-scale FSI problem to a nonlinear elliptic equation for the averaged pressure and displacements at the coarse scale. The proposed MsFEM schemes correctly transfer the appropriate physics from the fine to the coarse scale. Several numerical examples which demonstrate the methods are also presented.