Exploration of new superconductors has always been one of the research directions in condensed matter physics. We report here a new layered heterostructure of [(Fe,Al)(OH)2][FeSe]1.2, which is synthesized by the hydrothermal ion-exchange technique. The structure is suggested by a combination of X-ray powder diffraction and the electron diffraction (ED). [(Fe,Al)(OH)2][FeSe]1.2 is composed of the alternating stacking of tetragonal FeSe layer and hexagonal (Fe,Al)(OH)2 layer. In [(Fe,Al)(OH)2][FeSe]1.2, there exists mismatch between the FeSe sub-layer and (Fe,Al)(OH)2 sub-layer, and the lattice of the layered heterostructure is quasi-commensurate. The as-synthesized [(Fe,Al)(OH)2][FeSe]1.2 is non-superconducting due to the Fe vacancies in the FeSe layer. The superconductivity with a Tc of 40 K can be achieved after a lithiation process, which is due to the elimination of the Fe vacancies in the FeSe layer. The Tc is nearly the same as that of (Li,Fe)OHFeSe although the structure of [(Fe,Al)(OH)2][FeSe]1.2 is quite different from that of (Li,Fe)OHFeSe. The new layered heterostructure of [(Fe,Al)(OH)2][FeSe]1.2 contains an iron selenium tetragonal lattice interleaved with a hexagonal metal hydroxide lattice. These results indicate that the superconductivity is very robust for FeSe-based superconductors. It opens a path for exploring super-conductivity in iron-base superconductors.