Pore structure is an important composition of concrete microstructure and affects the macroscopic properties of concrete. This paper aims to study the effect of the substitution of municipal solid waste incineration bottom ash (MSWIBA) for natural sand on the pore structure and compressive strength of concrete. Nuclear magnetic resonance technology was employed to investigate the porosity and the variation character of the pore size distribution for concrete with MSWIBA. Meanwhile, according to the fractal theory, the fractal characteristics of pores were explored, and the fractal dimension of each pore size interval and the overall fractal dimension were obtained. Moreover, the grey entropy correlation degree between each pore size ratio, porosity, fractal dimension, and compressive strength was discussed. The results show that the porosity of concrete increases, and the proportion of harmless pores and compressive strength decrease with the increase of the replacement of natural sand with MSWIBA. Furthermore, the fractal dimension decreases with the increase of the content of MSWIBA. The fractal dimension increases and the pore structure is improved with age due to the potential hydraulic properties of MSWIBA. Meanwhile, the overall fractal dimension and the proportion of harmless pores of concrete with MSWIBA have the greatest influence on the compressive strength based on the grey entropy correlation degree analysis.