Understanding the size-dependent oxygen affinity of small Au nanoparticles (NPs) and nanoclusters (NCs) is central to the rational design of Au oxidation catalysts. However, relevant complete experimental or computational information on the intrinsic catalytic nature of Au NPs/NCs is scarce. Here, to provide fundamental insights into the intrinsic size- and coordination-dependent catalytic nature of free-standing small Au NPs/NCs for oxidation reactions, we constructed small unsupported Au (n = 1-10, 13, 19, 20, 25, 38, and 55) NCs and scrutinized their oxygen-adsorption chemistry and corresponding CO oxidation activity using density functional theory (DFT) calculations. Strong oxygen binding to Au-n NCs is essential for facile CO oxidation. Among our studied Au NCs, only the tiny Au-3, Au-5, and Au-7 NCs strongly bound O-2 and CO. The subsequent CO oxidation pathways studied by DFT confirmed that Au-5 exhibited the highest CO oxidation rate among the studied Au NCs. We observed that only highly limited, tiny Au NCs with a specific structural motif can catalyze CO oxidation themselves. We observed that a delicate balance between the energy of CO adsorption and that of O-2 adsorption is required to maximize the catalytic activity of Au NCs with respect to CO oxidation