The recently introduced Korringa-Kohn-Rostoker nonlocal coherent-potential approximation (KKR-NLCPA) provides a sound basis for systematically including important environmental effects within an ab initio description of disordered systems. Here we propose a fully relativistic formulation of the KKR-NLCPA which is designed for the treatment of magnetically-ordered alloys. Crucial to its implementation is a reformulation of the basic algorithm and a symmetrization of the fundamental coarse-graining procedure, which we describe in detail. As a first application of the approach we study the electronic and magnetic properties of the ferromagnetic FePt system.