Nano-shaped CeO2 (i.e., polyhedra, rods and cubes) and CeO2 without defined morphology were compared as supports of AuCu/CeO2 catalysts in the CO removal of actual syngas streams. Catalyst characterization indicates that oxygen vacancies, exposed CeO2 crystal planes, surface area and the interaction between active metals and support translate into changes in the catalytic performance on each nano-shape of CeO2. CeO2 nano-polyhedra and nano-rods show the higher activity and selectivity due to their high surface area and the presence of both {111} and {100} lattice planes. However, nano-rods are susceptible of losing CO2-selectivity under continuous operation due to the presence of an additional and unstable {110} lattice plane. Therefore, an AuCu catalyst supported on nano-polyhedra CeO2 ensures complete CO removal (i.e., <100 ppm) from an actual syngas stream for 48 h. These results are a contribution to the development of a simple, continuous and robust system for fuel-cell grade H2 production.