A series of nanocrystalline cellulose (NCC)-mesoporous silica composites (NCC-AO) with attached double-amidoxime groups is synthesized and examined for CO2 sorption at both ambient (25 °C) and elevated temperatures (120 °C). NCC-AO composites showed high CO2 uptakes at ambient pressure, namely, 3.30 mmol g−1 at 25 °C and 5.54 mmol g−1 at 120 °C. The CO2 sorption capacity of NCC-AO at 1 atm and 120 °C is very high and exceeds the values reported so far for other sorbents under the same conditions. NCC-AO sorbents exhibited very good recyclability and were stable after ten successive adsorption/desorption cycles with negligible losses of the sorption capacity. Due to the high sorption capacity, reusability, thermal stability, relatively low cost and simple synthesis route, the NCC-AO composites show good potential as effective sorbents and catalysts, including CO2 sorption at elevated temperatures.