Co-based Heusler phases, for example Co(Cr,Fe,Al), are considered as potential half-metallic ferromagnets with full spin polarization at the Fermi level and are therefore not only interesting from a fundamental point of view but also for their prospective technological exploitation. For successful materials design via selection of candidates towards desired properties as well as practical synthesis, knowledge of the relevant thermodynamic phase diagrams is an important aspect. However, the materials of interest constitute quaternary systems, where such knowledge is scarce. The importance of thermodynamic understanding is underlined by previous experimental findings, which report that the phase formation of the desired structurally ordered Co(Cr,Fe,Al) is not straightforward due to thermodynamic instabilities. In this work, we revisit the quaternary region of the CoCr-CoAl-CoFe section of the thermodynamic phase diagram through DFT and thermodynamic calculations. The regular solution model indicates the formation of an immiscibility region centered around a pseudoternary critical point at T_c = 1412 K and the composition CoFe_0.2Cr_0.4Al_0.4. FP-LAPW ab initio calculations of the enthalpy of mixing show an energetically favorable minimum at the CoCr_0.125Fe_0.25Al_0.625 composition and a local maximum around CoFe_0.125Cr_0.375Al_0.5 which corresponds to the region of immiscibility and matches the area of the binodal/spinodal decomposition resulting from the regular solution model. We discuss three types of substitution: Al for Cr, Al for Fe, and Al for Cr/Fe with special focus on the formation of different structural motifs, specifically on the order- and disorder, depending on the Cr/Fe ratio. Chemical bonding and magnetic properties of selected compositions are calculated and analyzed. Our results underline the significance of careful consideration of thermodynamic phase formation for materials design and consequently for machine learning approaches towards practical realization of functional materials.