We elucidate the microscopic mechanism of the weakening of the hydrophobicity at low temperatures by investigating cold denaturation of a protein. We employ an elaborate statistical-mechanical theory combined with a realistic water model. At low temperatures, the ordered structure with enhanced hydrogen bonds of water molecules is formed near nonpolar groups, leading to entropic loss and energy gain which are both quite large. However, they are canceled out and make no contribution to the free-energy change. We argue that a different factor, which is responsible for the weakening of the hydrophobicity at low temperatures, induces cold denaturation.