We report on the ice-templated preparation and sodium storage of ultrasmall SnO2 nanoparticles (3-4 nm) embedded in three-dimensional (3D) graphene (SnO2@3DG). SnO2@3DG was fabricated by hydrothermal assembly with ice-templated 3DG and a tin source. The structure and morphology analyses showed that 3DG has an interconnected porous architecture with a large pore volume of 0.578 cm3·g-1 and a high surface area of 470.5 m2·g-1. In comparison, SnO2@3DG exhibited a pore volume of 0.321 cm3·g-1 and a surface area of 237.7 m2·g-1 with a homogeneous distribution of ultrasmall SnO2 nanoparticles in a 3DG network. SnO2@3DG showed a discharge capacity of 1, 155 mA·h·g-1 in the initial cycle, a reversible capacity of 432 mA·h·g-1 after 200 cycles at 100 mA·g-1 (with capacity retention of 85.7% relative to that in the second cycle), and a discharge capacity of 210 mA·h·g-1 at a high rate of 800 mA·g-1. This is due to the high distribution of SnO2 nanoparticles in the 3DG network and the enhanced facilitation of electron/ion transport in the electrode.