Recent experiments on pure fluids have identified distinct liquid-like and gas-like regimes even under supercritical conditions. The supercritical liquid-gas transition is marked by maxima in response functions that define a line emanating from the critical point, referred to as Widom line. However, the structure of analogous state transitions in mixtures of supercritical fluids has not been determined, and it is not clear whether a Widom line can be identified for binary mixtures. Here, we present first evidence for the existence of multiple Widom lines in binary mixtures from molecular dynamics simulations. By considering mixtures of noble gases, we show that, depending on the phase behavior, mixtures transition from a liquid-like to a gas-like regime via distinctly different pathways, leading to phase relationships of surprising complexity and variety. Specifically, we show that miscible binary mixtures have behavior analogous to a pure fluid and the supercritical state space is characterized by a single liquid-gas transition. In contrast, immiscible binary mixture undergo a phase separation in which the clusters transition separately at different temperatures, resulting in multiple distinct Widom lines. The presence of this unique transition behavior emphasizes the complexity of the supercritical state to be expected in high-order mixtures of practical relevance.