The stability of (Crx,V1-x)2AlC MAX phases, materials of interest for a variety of magnetic as well as high temperature applications, has been studied using density-functional-theory first-principles calculations. The enthalpy of mixing predicts these alloys to be unstable towards unmixing at 0 K. The calculations also predict, however, that these phases would be thermally stabilised by configurational entropy at temperatures well below the values used for synthesis. The temperature Ts below which they become unstable is found to be quite sensitive to the presence of magnetic moments on Cr ions, as well as to the material’s magnetic order, in addition to chemical order and composition. Allowing for magnetism, the value of Ts for (Cr0.5,V0.5)2AlC with chemically disordered Cr and V atoms, is estimated to be between 516 K and 645 K depending on the level of theory, while if constrained to spin-paired, Ts drops to 142 K. Antiferromagnetic spin arrangements are found to be favored. The combination of antiferromagnetic frustration and configurational disorder should give rise to interesting spin textures at low temperatures.