The influence of composition on microstructural phase stability has been assessed for an emerging class of Co-based superalloys. This has been achieved using a combinatorial approach that incorporates both material synthesis and state-of-the-art characterization techniques. A compositionally graded Co-11Al-xW-yTa alloy (x ≤10, y=10-x, all in wt%) was produced using Laser Engineered Net-Shaping (LENS™) and subsequently solutionized and water quenched. At selected locations along the gradient, the microstructures present were characterized in detail, and phase identification was conducted on site-specific thin specimens using transmission electron microscopy (TEM), providing details regarding the earliest stages of microstructural evolution in these alloys. The partitioning behavior of the alloying elements W, Ta and Al was characterized using the 3D Local Electrode Atom Probe, revealing the existence of Co-rich clusters. In addition high resolution TEM and precession electron diffraction have revealed and confirmed that these clusters are a pseudomorphic bcc structure that has resulted from the decomposition of a B2 ordered region. Though bcc Co has previously been reported in some thin-film multilayers, owing to the relative stabilities of the bcc phase and the fcc phase, this observation has not been previously reported in bulk structural materials. It is argued that this nanoscaled pseudomorphic bcc Co phase may be a precursor to the fcc phase.