Nanostructured abradable coatings were produced via air plasma spray (APS) and compared to conventional abradable coatings based on the composite CoNiCrAlY+BN+polyester also sprayed via APS. The microstructures of the coatings were analyzed using SEM and the hardness determined via Rockwell Y measurements. It was possible to engineer nanostructured abradables with a high degree of plasticity by controlling the amount, morphology and distribution of the nanostructured phase embedded in the coating microstructure. Rub-rig tests were performed for both types of coatings under different blade tip speeds and seal incursion rates simulating operating conditions of gas turbines. The resulting incursion force, blade and seal wear have been discussed and analyzed. The nanostructured abradables exhibited good performance indicating that abradable coatings engineered in this fashion have potential for industrial application at elevated temperatures.