We present a scheme for the first-principles calculation of EPR lineshapes for continuous-wave-EPR spectroscopy (cw-EPR) of spin centers in complex chemical environments. We specifically focus on poorly characterized systems, e.g. powders and frozen glasses with variable microsolvation structures. Our approach is based on ab initio molecular dynamics simulations and ab initio calculations of the ensemble of g- and A-tensors along the trajectory. The method incorporates temperature effects as well as the full anharmonicity of the intra- and intermolecular degrees of freedom of the system. We apply this scheme to compute the lineshape of a prototypical spin probe, the nitrosodisulfonate dianionic radical (Fremy's salt), dissolved in a 50 : 50 mixture of water and methanol. We are able to determine the specific effect of variations of local solvent composition and microsolvation structure on the cw-EPR lineshape. Our molecular dynamics reveal a highly anisotropic solvation structure with distinct spatial preferences for water and methanol around Fremy's salt that can be traced back to a combination of steric and polar influences. The overall solvation structure and conformational preferences of Fremy's salt as found in our MD simulations agree very well with the results obtained from EPR and orientation-selective ENDOR spectroscopy performed on the frozen glass. The simulated EPR lineshapes show good agreement with the experimental spectra. When combined with our MD results, they characterize the lineshape dependence on local morphological fluctuations.