We investigated the carbon monoxide (CO) gas-sensing properties of nanostructured Al-doped zinc oxide thin films deposited on self-assembled Au nanodots (ZnO/Au thin films). The Al-doped ZnO thin film was deposited onto the structure by rf sputtering, resulting in a gas-sensing element comprising a ZnO-based active layer with an embedded Pt/Ti electrode covered by the self-assembled Au nanodots. Prior to the growth of the active ZnO layer, the Au nanodots were formed via annealing a thin Au layer with a thickness of 2 nm at a moderate temperature of $500^{circ}C$. It was found that the ZnO/Au nanostructured thin film gas sensors showed a high maximum sensitivity to CO gas at $250^{circ}C$ and a low CO detection limit of 5 ppm in dry air. Furthermore, the ZnO/Au thin film CO gas sensors exhibited fast response and recovery behaviors. The observed excellent CO gas-sensing properties of the nanostructured ZnO/Au thin films can be ascribed to the Au nanodots, acting as both a nucleation layer for the formation of the ZnO nanostructure and a catalyst in the CO surface reaction. These results suggest that the ZnO thin films deposited on self-assembled Au nanodots are promising for practical high-performance CO gas sensors.