Natural rubber/carbon nanotubes composite foams (F-NR/CNTs) with high electrical conductivity and excellent electromagnetic interference (EMI) performance were developed through a multi-step process. CNTs were assembled on natural rubber particles and then a pre-crosslinking treatment was applied. Such composite structures were foamed with supercritical carbon dioxide with a batch process and finally foamed composite samples were post-crosslinked. Closed-cell porous structure and segregated CNT network were induced in the resulting foams. The expansion ratio ranged between 0.3 and 2.7, the cell size was between 4 and 23 μm and the cell density was in the order of 108 cells/cm3. Thanks to the segregated network morphology, composite foams exhibited good mechanical properties, and the electrical conductivity was proportional to the CNT content. Owing to the multiple radiation reflections and scattering between the cell-matrix interfaces, the composite foams showed a specific shielding effectiveness (SSE) up to 312.69 dB cm2/g for composite foams containing 6.4wt% of CNTs. This performance is significantly higher than those already published for rubber composites containing comparable nanocomposite filler content. More importantly, the shielding effect is mostly due to absorption, implying that most of incident electromagnetic radiation is dissipated. This work provides the fundamentals for the design of innovative lightweight and efficient EMI shielding foams, characterized by a three-dimensional segregated CNTs network with valuable potentials in the electronics and aerospace industries.