Developing a new type of CO gas sensor with high response, good reproducibility, and short response/recovery time is of great significance in medical fields, especially during anesthesia. During mechanical ventilation, CO gas will be produced by CO2 absorbent. Herein, novel interconnected CeO2 nanofibers with an average diameter of 150 nm are firstly prepared by electrospinning. The results show that the received nanofibers are mainly composed of fluorite-structured CeO2 crystals with oxygen vacancies as well as the adsorbed oxygen species on the fiber surface. It is found that there is no agglomeration and sintering for the nanofibers even after annealing at 1000°C. The interconnected nanofibers exhibit excellent gas sensing performance to CO gas at an optimum operating temperature of 450°C, where the gas sensing response value is 2.82. And the nanofibers also exhibit excellent gas sensing reproducibility, fast response/recovery rate (2 s/4 s), and high response value-concentration correlation toward CO. This study provides a simple approach to interconnected CeO2 nanofibers for potential gas sensor application.