We report the studies of emission from a novel random amplifying medium that we term a ``Levy Laser'' due to the non-Gaussian statistical nature of its emission over the ensemble of random realizations. It is observed that the amplification is dominated by certain improbable events that are ``larger than rare'', which give the intensity statistics a Levy like ``fat tail''. This, to the best of our knowledge, provides the first experimental realization of Levy flight in optics in a random amplifying medium.