Before coaching the senior side, Gonçalves was in charge of the Under-20 team, with which he won the African Youth Championship, before assuming control of the senior team in 2004 for Angola's World Cup qualify campaign, in which he sprang one of the continent's biggest ever upsets when Angola managed to pip Nigeria to the top of a tough qualifying group, ensuring qualification to the pinnacle of world football in 2006.
Perceived by many as one of the weaker nations in the World Cup, Angola were paired with former colonial masters and Euro 2004 runners-up Portugal, then FIFA World Ranked 4th nation and seeds Mexico, and previous qualifier Iran in Group D. Despite predictions that Angola would be the whipping boys of the group, Gonçalves employed disciplined and organised tactics amongst his defence, and coupled this with a strong midfield and quick wingers both capable of retaining possession in the middle of the park and also launching pacey counter-attacks, with onus particularly placed on playmaker Figueiredo, wingers Ze Kalanga and Edson, and lone striker and national icon Akwa.
Once again disciplining his defence to be watertight, and also entrusting free agent Joao Ricardo in goal, Angola kept a clean sheet against the Mexicans to draw 0–0 against the odds.
Gonçalves's impressive stewardship of the much unfavoured Angolans meant that remarkably the then 57th FIFA Ranked team in the world had a conceivable chance of qualifying from the group as runners-up.
Gonçalves's resolute defending plus quick counter-attacking tactics continued into his team's match against Iran, with Flávio creating history by scoring Angola's first ever goal in the World Cup.