Rödhuvad törnskata är 17–19 centimeter lång och har en lång stjärt inräknat om omkring 8 centimeter. Den har den för törnskatorna typiska kroppsformen, med kraftig näbb och en kompakt kropp med förhållandevis lång stjärt.
Den adulta fågelns fjäderdräkten är främst svart, vit med brunrött huvud. Könen går att skilja åt genom att honans teckning är något ljusare, där det svarta går mer åt mörkgrått och det röda mer åt orangebrunt. Honan är också något mindre än hanen.
Som juvenil och under första vintern är den på ovansidan vattrad i brunt, grått och vitt och påminner om en ljusare och gråare variant av juvenil törnskata.
Fågelarter i grupp Flugsnappare-Törnskator
Grå flugsnappare | Halsbandsflugsnappare | Mindre flugsnappare | Bläsand | Blåmes | Entita | Pungmes | Skäggmes | Stjärtmes | Svartmes | Talgoxe | Talltita | Tofsmes | Klippnötväcka | Nötväcka | Trädgårdsträdkrypare | Trädkrypare | Isabellatörnskata | Masktörnskata | Rödhuvad törnskata | Svartpannad törnskata | Törnskata | Varfågel | Ökenvarfågel