3 września 2004 roku podpisał kontrakt z Colchester United. W nowym zespole zadebiutował dzień później w spotkaniu z Swindon Town. 29 września w zremisowanym 1:1 spotkaniu z Southend United w ramach rozgrywek Football League Trophy strzelił pierwszą bramkę. Od czasu przyjścia Garcia w zespole Colchester United był podstawowym graczem. W klubie tym grał przez trzy sezony, w czasie których zagrał w 82 ligowych meczach. Poza tym w sezonie 2005/2006 jego klub awansował do Championship.
Następnie, 2 lipca 2007 roku przeszedł do Hull City, podpisując trzyletni kontrakt. W zespole tym zadebiutował 11 sierpnia w ligowym spotkaniu z Plymouth Argyle. Cztery dni później w meczu Pucharu Ligi z Crewe Alexandra zdobył pierwszego gola. Szybko stał się jednym z podstawowych zawodników klubu. Sezon 2007/2008 zakończył z 38 ligowymi występami. Hull awansowało także do Premier League. Jego gol, który zdobył 4 marca w meczu z Burnley został wybrany najlepszą bramką klubu. W sezonie 2008/2009 zagrał w mniejszej liczbie spotkań i wraz z klubem utrzymał się w lidze.