The molecular-level details of the formation of mixed gas hydrates remain elusive despite their significance for a variety of scientific and industrial applications. In this study, extensive molecular simulations have been performed to examine the behavior of CH4/H2S mixed hydrate nucleation utilizing two different simulation setups varying in compositions and temperatures. The observed behavior exhibits similar phenomenology across the various systems once differences in nucleation rates and guest uptake are accounted for. We find that CH4 is always enriched in the hydrate phase while the aqueous phase is enriched in H2S. Even with H2S as a minor component (i.e., 10% mole fraction), the system can mirror the overall nucleation kinetics of pure H2S hydrate systems with CH4-dominant nuclei. Through analyses of cages and their transitions, nonstandard cages, particularly those with 12 faces (e.g., 51062), have been found to be key intermediate cage types in the early stage of nucleation. Additionally, we present previously unreported cage types comprising heptagonal faces (e.g., 596271) as having a significant role in the early-stage gas hydrate structural transitions.