Black holes are one of the most fascinating predictions of the General Theory of Relativity. According to the conventional picture that emerged in the 1970s as a corollary of the uniqueness theorems, black holes are extremely constrained objects, determined by only a few global charges. For instance, two black holes with the same total mass and angular momentum must be precisely equal, in sharp contrast with stars. Such simplicity of black holes became immortalized in John Wheeler's mantra "Black holes have no hair". In this talk, I will start by reviewing the history and some key physical/mathematical properties of black holes in General Relativity. I will then discuss a novel mechanism that allows black holes to have 'hair' and challenges the standard paradigm. Some possible astrophysical consequences will be addressed. http://gravitation.web.ua.pt/herdeiro.