We investigate flows interacting with square and fractal shape multi-scale structures in the compressible regime for Mach numbers under subsonic and supersonic upstream conditions using large-eddy simulations. We also aim at identifying similarities and differences that these interactions have with the corresponding interactions in the canonical incompressible flow problem. To account for the geometrical complexity associated with the fractal structures, we apply an immersed boundary method to model the no-slip boundary condition at the solid surfaces, with adequate mesh resolution in the vicinity of the small fractal features. We validate the numerical results through extensive comparisons with experimental wind tunnel measurements at a low Mach number. Similar to the incompressible flow case results, we find a breakup of the flow structures by the fractal plate and an increase in turbulent mixing in the downstream direction. As the Mach number increases, we observe noticeable wake meandering and higher spread rate of the wake in the lateral direction perpendicular to the streamwise–spanwise plane. Although not significant, we quantify the difference between the square and the fractal plates using two-point velocity correlations across the Mach number range. The wakes generated by the fractal plate in the compressible regime showed lower turbulent kinetic energy and energy spectra levels compared to those of the square case. Moreover, results in terms of the near-field pressure spectra seem to indicate that the fractal plate has the potential to reduce the aerodynamic noise.