Melissa Gregory and Denis Petukhov teamed up in the Fall of 2000 after corresponding via the internet. For the 2006/07 season, they relocated to Newark, Delaware to train under coaches Natalia Linichuk and Gennady Karponosov.

The 2006/07 international season has been successful for Gregory and Pethukov as they won silver at Skate America and bronze at NHK Trophy, which qualified them for the Grand Prix Final for the first time (where they finished in 6th).

Gregory and Pethukov have medaled in every appearance at the National Championships including bronze at the 2002 and 2003 championships and silver at the 2004, 2005 and 2006 events.