Long-time-scale molecular dynamics simulations are presented of the spontaneous formation of methane hydrate at a methane/liquid water interface. The water film was prepared at 300 K, 30 bar and showed no significant hydrate order. On crash cooling to 250 K, 300 bar (about 20 K subcooling), the system showed a rapid growth of hydrate clusters. Contrary to popular models for hydrate nucleation, the clusters formed first as two-dimensional arrangements and only later into three-dimensional cage structures; the results are, however, consistent with the local order model proposed recently. The hydrate clusters showed clear signatures of the type II hydrate structure even though the type I structure is the thermodynamically stable form for methane hydrate; this is in accord with the results of recent diffraction experiments.