In this work, we present the hydrate phase behavior of methane, ethane, propane, and water systems. Phase diagrams for the ternary and each binary hydrocarbon mixture with excess water have been generated at 277.6 K (similar to deep sea floor temperature) using a Gibbs free energy minimization flash routine. Each pseudo-binary phase diagram (excluding water) is related to the pseudo-ternary. The main focus is the phase behavior of the pseudo-ternary hydrocarbon mixture around the incipient hydrate formation pressures at 277.6 K. Phase diagrams at this temperature are presented for pressures ranging from 10 to 45 atm. Unexpected phenomena such as the coexistence of hydrate structures, solid melting on pressure increases, and several four phase regions (L-w-sI-sII-V and L-w-sI-sII-L-hc) were encountered. Similar phenomena may exist when a real natural gas contacts water.