We propose an iteratively adaptive Multi-scale Finite Element Method (MsFEM) for elliptic PDEs with rough coefficients. The choice of the local boundary conditions for the multi-sale basis functions determines the accuracy of the MsFEM numerical solution, and one needs to incorporate the global information of the elliptic equation into the local boundary conditions of the multi-scale basis functions to recover the underlying fine-mesh solution of the equation. In our proposed iteratively adaptive method, we achieve this global-to-local information transfer through the combination of coarse-mesh solving using adaptive multi-scale basis functions and fine-mesh smoothing operations. In each iteration step, we first update the multi-scale basis functions based on the approximate numerical solutions of the previous iteration steps, and obtain the coarse-mesh approximate solution using a Galerkin projection. Then we apply several steps of smoothing operations to the coarse-mesh approximate solution on the underlying fine mesh to get the updated approximate numerical solution. The proposed algorithm can be viewed as a nonlinear two-level multi-grid method with the restriction and prolongation operators adapted to the approximate numerical solutions of the previous iteration steps. Convergence analysis of the proposed algorithm is carried out under the framework of two-level multi-grid method, and the harmonic coordinates are employed to establish the approximation property of the adaptive multi-scale basis functions. We demonstrate the efficiency of our proposed multi-scale methods through several numerical examples including a multi-scale coefficient problem, a high-contrast interface problem, and a convection-dominated diffusion problem.