Ogółem w sezonie 2003/2004 dwukrotnie rozpoczynał spotkania od pierwszych minut i osiem razy wszedł z ławki rezerwowych, występował także w zespole młodzieżowym, pomagając mu dostać się do najlepszej szesnastki Młodzieżowego Pucharu Anglii . Na krótko przed końcem sezonu podpisał swój pierwszy profesjonalny kontrakt w karierze, wiążąc się z klubem na okres trzech lat.
W kolejnym sezonie Jarvis wywalczył pewne miejsce w wyjściowym składzie, występując w 30 ligowych meczach, pomimo że wskutek przepukliny pauzował przez pięć tygodni. Pierwszego gola dla klubu zdobył w wygranym spotkaniu z Wolverhampton Wanderers, 30 października 2004 roku. Mimo to Gillingham nie zdołało uniknąć spadku z ligi. W sezonie 2005/2006 Jarvis regularnie występował w składzie, zdobył siedem bramek, co statystycznie jest jego najlepszym sezonem w karierze.
W połowie sezonu 2006/2007 Gillingham zaproponowało zawodnikowi nowy, oparty na lepszych warunkach, kontrakt. Jarvis odrzucił ofertę, zaś później poprzez swojego agenta stwierdził, że chętnie pozostanie na Priestfield Stadium, jeżeli klub „udowodni, że będzie mógł on spełnić w nim swe ambicje”. Wiele klubów występujących w Premier League i Championship wykazało zainteresowanie pomocnikiem.