We describe an infinite-dimensional algebra of hidden symmetries for the self-dual gravity equations. Besides the known diffeomorphism-type symmetries (affine extension of w(infinity) algebra), this algebra contains new hidden symmetries, which are an affine extension of the Lorentz rotations. The full symmetry algebra has both Kac-Moody and Virasoro-like generators, whose exponentiation maps solutions of the field equations to other solutions. Relations to problems of string theories are briefly discussed.