The onset of gas hydrate nucleation is greatly affected by the thermal history of the water that forms its lattice structure. Hydrate formation experiments were performed in a 72 L pressure vessel by injecting bubbles of carbon dioxide through a 1 L tube at hydrate formation pressures (1.4 to 3.7 MPa) and temperatures (2 to 5 °C). The results revealed that when even a small fraction (e.g., 5–35%) of the water in which the hydrate formed was recently thawed the overpressure for nucleation was reduced by an average of 50% as compared to untreated distilled water. This observation was confirmed by an analysis of variance (ANOVA) test that indicated that recently thawed water required a significantly lower overpressure compared to the untreated distilled water. In experiments where hydrate nucleated at low overpressure (e.g., 0.75 MPa), hydrate formed at the vapor-liquid interface, encrusting the bubbles with less than 1 g of hydrate accumulation in the first minute. When a higher overpressure was required for nucleation (e.g., 1.3 MPa), hydrate was observed to form abruptly not only on bubbles but also from the bulk liquid phase, typically accumulating a mass of more than 100 g in the first few seconds. Our results show that initiation of hydrate formation is strongly influenced by temperature-dependent pre-structuring of water molecules prior to their contact with gas. Although as little as a 5% volume fraction of pre-structured water may decrease the required overpressure, once hydrate formation commences the mass of hydrate accumulation is dependent on the overpressure.