Nonlinear and dispersive transmission impairments in coherent fiber-optic communication systems are often compensated by reverting the nonlinear Schrodinger equation, which describes the evolution of the signal in the link, numerically. This technique is known as digital backpropagation. Typical digital backpropagation algorithms are based on split-step Fourier methods in which the signal has to be discretized in time and space. The need to discretize in both time and space however makes the real-time implementation of digital backpropagation a challenging problem. In this paper, a new fast algorithm for digital backpropagation based on nonlinear Fourier transforms is presented. Aiming at a proof of concept, the main emphasis will be put on fibers with normal dispersion in order to avoid the issue of solitonic components in the signal. However, it is demonstrated that the algorithm also works for anomalous dispersion if the signal power is low enough. Since the spatial evolution of a signal governed by the nonlinear Schrodinger equation can be reverted analytically in the nonlinear Fourier domain through simple phase-shifts, there is no need to discretize the spatial domain. The proposed algorithm requires only $mathcal{O}(Dlog^{2}D)$ floating point operations to backpropagate a signal given by $D$ samples, independently of the fibers length, and is therefore highly promising for real-time implementations. The merits of this new approach are illustrated through numerical simulations.