Marchena made his senior team debut on 21 August 2002, playing in a testimonial match for Hungarian legend Ferenc Puskás in Budapest, just after the 2002 FIFA World Cup in South Korea and Japan. Subsequently, he was part of the nation's squads at UEFA Euro 2004, where he was chosen at the last minute by coach Iñaki Sáez as a strategic move to bolster his squad defensively; while Spain did not do well in the tournament and bowed out in the early stages, he did manage two appearances, although he also picked up two yellow cards while doing so.