Zinc oxide has widespread use in diverse applications due to its distinct properties. Many of these applications benefit from controlling the morphology on the nanoscale, where for example gas sensing is strongly enhanced for high surface-to-volume ratios. In this work the formation of novel ZnO nanobrushes by plasma etching treatment as a new approach is presented. The morphology and structure of the ZnO nanobrushes are studied in detail by transmission and scanning electron microscopy. It is revealed that ZnO nanobrush structures are fabricated by self-patterned preferential etching of ZnO microtetrapods in a hydrogen-acetylene plasma. The etching process was found to be most effective at 1% C2H2 admixture. Nanowire arrays are formed enabled by sidewall passivation due to a-C:H deposition. The nanobrush structures are further stabilized by simultaneous deposition of a SiOx layer from the opposite direction. Highly sensitive (gas response S = 148), selective, and fast (response time 15 s, recovery time 6 s) hydrogen sensors are fabricated from single nanobrushes. Single nanobrush sensors show enhanced sensing performance in increased gas response S of at least 10 times and improved response as well as recovery times when compared to nonporous single ZnO nanorod sensors due to the small diameters (≈50 nm) of the formed nanowires as well as the strongly enhanced surface-to-volume ratio of the nanobrushes by a factor of more than 10.