Innovative structured catalysts based on nanoparticles of gold supported on activated carbon fibers (ACF) in the form of woven fabrics are presented for low-temperature CO oxidation. Gold was deposited by adsorption from aqueous solution of ethylenediamine complex [Au(en)2]Cl3 followed by reduction in hydrogen. The catalysts were studied under transient reaction conditions and characterized by high-resolution transmission electron microscopy (HRTEM) and X-ray energy dispersive analysis (EDS). HRTEM-EDS shows that gold is present on the surface of Au/ACF catalyst in the form of metallic particles with sizes of ~2.5–5 and ~30–50 nm. A predeposition of iron oxide on the ACF was beneficial for the Au dispersion and catalytic activity in CO oxidation. Gold particles in the Au/FeOx/ACF samples were not in direct contact with the Fe2O3 phase and their size was smaller than without doping by iron oxide. The mechanism of catalyst formation, its morphology, and the influence of preparative conditions are discussed. The activity of Au/FeOx/ACF was substantially higher as compared to Au/Al2O3 and Au/FeOx/Al2O3 catalysts. A reductive pretreatment with H2 was necessary to activate the catalyst, but the activity decreased rapidly in CO/O2 atmosphere. Addition of hydrogen or water vapors to the reaction mixture increases the catalyst activity.