We show that the symmetry algebra, of the SL(2,R)k/U(1) coset model is a non-linear deformation of W∞, characterized by k. This is a universal W-algebra which linearizes in the large k limit and truncates to WN for k = − N. Using the theory of non-compact parafermions we construct a free field realization of the non-linear W∞ in terms of two bosons with background charge. The W-characters of all unitary SL(2,R)/U(1) representations are computed. Applications to the physics of 2-d black hole backgrounds are also discussed and connections with the KP approach to c=1 string theory are outlined.