From A Wiki of Ice and Fire
Coldhands astride his great elk - © Zippo514
|Book(s)|| A Storm of Swords (Appears)|
A Feast for Crows (Mentioned)
A Dance with Dragons (Appears)
Coldhands is a mysterious figure from beyond the Wall. He looks like a wight dressed in the black of the Night's Watch with a scarf concealing his face, a corpse with hands black from pooled and congealed blood, but is intelligent and seemingly benign.
Summer does not like the way Coldhands smells - dead meat, dry blood, a faint whiff of rot. And cold. Cold all over. Though Coldhands is often described as dead, but still alive, his eyes are described as black, in contrast of the light blue of wights and Others.
A Storm of Swords
Coldhands saved Samwell Tarly, Gilly and her son when they were beset by wights and were lost north of the Wall, while fleeing Craster's Keep. He took the two under his protection and brought them back and through the wall, by the Black Gate located underneath it. He could not pass through himself, due to the wall's magic, but he charged them to bring him Bran Stark and his companions who Coldhands was expecting. He looks and talks as if he was a ranger of the Night's Watch. 
A Dance with Dragons
Coldhands guides Bran Stark, Hodor, Meera and Jojen Reed to the last Greenseer beyond the Wall. Along the way he kills men of the Night's Watch. Bran, having warged into Summer, discovers this and confronts him in the abandoned village. There they discover that Coldhands is indeed dead, but continues to refuse to show his face. However unknown to Bran was that the men Coldhands killed were the surviving traitors responsible for the Mutiny at Craster's Keep.
|“||"They killed him long ago".||”|
|“||Your monster, Brandon Stark.||”|