W nano-structures (fuzz), produced in the linear high plasma device, NAGDIS, were exposed to TEXTOR edge plasmas (ohmic He/D mixed plasma and pure D plasma) to study formation, erosion and C deposition on W fuzz in tokamak plasmas for the first time. Fuzz layers were either completely eroded or covered by C deposit. There was no clear indication of W fuzz growth under the present conditions. There was no significant difference of C deposition between ‘thick’ fuzz (500–600nm in thickness) and ‘thin’ fuzz (300–400nm) in the He/D plasma. On the W fuzz surface, C deposition was enhanced probably due to reduction of effective sputtering yield and effective reflection coefficient of carbon ions, similar to roughness effects. Formation and erosion of W fuzz in tokamak devices and role of impurities are discussed.