High pressure can fundamentally alter the electronic structure of elemental metals, leading to the unexpected formation of intermetallics with unusual structural features. In the present study, the phase stabilities and structural changes of Na-Fe intermetallics under pressure were studied using unbiased structure searching methods, combined with density functional theory calculations. Two intermetallics with stoichiometries Na3Fe and Na4Fe are found to be thermodynamically stable at pressures above 120 and 155 GPa, respectively. An interesting structural feature is that both have form a host-guest-like structure with Na sublattices constructed from small and large polygons similar to the host framework of the self-hosting incommensurate phases observed in Group I and II elements. Apart from the one-dimensional (1D) Fe chains running through the large channels, more interestingly, electrides are found to localize in the small channels between the layers. Electron topological analysis shows secondary bonding interactions between the Fe atoms and the interstitial electrides help to stabilize these structures.