Magnetic particle imaging (MPI) is an emerging medical imaging modality which is based on the non-linear response of magnetic nanoparticles to an applied magnetic field. It is an important feature of MPI that even fast dynamic processes can be captured for 3D volumes. The high temporal resolution in turn leads to large amounts of data which have to be handled efficiently. But as the system matrix of MPI is non-sparse, the image reconstruction gets computationally demanding. Therefore, currently only basic image reconstruction methods such as Tikhonov regularization are used. However, Tikhonov regularization is known to oversmooth edges in the reconstructed image and to have only a limited noise reducing effect. In this work, we develop an efficient edge preserving and noise reducing reconstruction method for MPI. As regularization model, we propose to use the nonnegative fused lasso model, and we devise a discretization that is adapted to the acquisition geometry of the preclinical MPI scanner considered in this work. We develop a customized solver based on a generalized forward-backward scheme which is particularly suitable for the dense and not well-structured system matrices in MPI. Already a non-optimized prototype implementation processes a 3D volume within a few seconds so that processing several frames per second seems amenable. We demonstrate the improvement in reconstruction quality over the state-of-the-art method in an experimental medical setup for an in-vitro angioplasty of a stenosis.