We present an analysis of MUSE observations obtained on the massive Frontier Fields cluster Abell 2744. This new dataset covers the entire multiply-imaged region around the cluster core. We measure spectroscopic redshifts for HST-selected continuum sources together with line emitters blindly detected in the datacube. The combined catalog consists of 514 spectroscopic redshifts (with 414 new identifications), including 156 cluster members and 326 magnified background sources. We use this redshift information to perform a strong-lensing analysis of all multiple images previously found in the deep Frontier Field images, and add three new MUSE-detected multiply-imaged systems with no obvious HST counterpart. The combined strong lensing constraints include a total of 60 systems producing 188 images altogether, out of which 29 systems and 83 images are spectroscopically confirmed, making Abell 2744 one of the most well-constrained clusters to date. A parametric mass model including two cluster-scale components in the core and several group-scale substructures at larger radii accurately reproduces all the spectroscopic multiple systems, reaching an rms of 0.67 in the image plane. Overall, the large number of spectroscopic redshifts gives us a robust model and we estimate the systematics on the mass density and magnification within the cluster core to be typically ~9%.