The factors mediating cation ordering in the scheelite-based molybdates and tungstates are discussed on the basis of the incommensurately modulated crystal structures of the CaEu2(BO4)4 (B = Mo, W) red phosphors solved from high-resolution synchrotron powder X-ray diffraction data. Monoclinic CaEu2(WO4)4 adopts a (3 + 1)-dimensionally modulated structure [superspace group I2/b(αβ0)00, a = 5.238 73(1)Å, b = 5.266 35(1) Å, c = 11.463 19(9) Å, γ = 91.1511(2)°, q = 0.56153(6)a* + 0.7708(9)b*, R(F) = 0.050, R(P) = 0.069], whereas tetragonal CaEu2(MoO4)4 is (3 + 2)-dimensionally modulated [superspace group I4₁/a(αβ0)00(-βα0)00, a = 5.238 672(7) Å, c = 11.548 43(2) Å, q1 = 0.55331(8)a* + 0.82068(9)b*, q2 = -0.82068(9)a* + 0.55331(8)b*, R(F) = 0.061, R(P) = 0.082]. In both cases the modulation arises from the ordering of the Ca/Eu cations and the cation vacancies at the A-sublattice of the parent scheelite ABO4 structure. The cation ordering is incomplete and better described with harmonic rather than with steplike occupational modulation functions. The structures respond to the variation of the effective charge and cation size at the A-position through the flexible geometry of the MoO4(2-) and WO4(2-) tetrahedra demonstrating an alternation of stretching the B-O bond lengths and bending the O-B-O bond angles. The tendency towards A-site cation ordering in scheelites is rationalized using the difference in ionic radii and concentration of the A-site vacancies as parameters and presented in the form of a structure map.