An immersed boundary-lattice Boltzmann method is developed for fluid-structure interactions involving non-Newtonian fluids (e.g., power-law fluid). In this method, the flexible structure (e.g., capsule) dynamics and the fluid dynamics are coupled by using the immersed boundary method. The incompressible viscous power-law fluid motion is obtained by solving the lattice Boltzmann equation. The non-Newtonian rheology is achieved by using a shear rate-dependant relaxation time in the lattice Boltzmann method. The non-Newtonian flow solver is then validated by considering a power-law flow in a straight channel which is one of the benchmark problems to validate an in-house solver. The numerical results present a good agreement with the analytical solutions for various values of power-law index. Finally, we apply this method to study the deformation of a capsule in a power-law shear flow by varying the Reynolds number from 0.025 to 0.1, dimensionless shear rate from 0.004 to 0.1, and power-law index from 0.2 to 1.8. It is found that the deformation of the capsule increases with the power-law index for different Reynolds numbers and nondimensional shear rates. In addition, the Reynolds number does not have significant effect on the capsule deformation in the flow regime considered. Moreover, the power-law index effect is stronger for larger dimensionless shear rate compared to smaller values.