Costa won his first top-level singles title in 1995 at Kitzbühel, beating the "King of Clay", Thomas Muster, in a five set final, and it was Muster's first of his only 2 losses on clay in 1995. Costa ended Muster's streak of 40 consecutive clay match wins and his 11 consecutive final wins . Costa won three further titles in 1996. In 1997, he won another two singles titles and was part of the Spanish team that won the World Team Cup. He won another two singles titles in 1998, including the Tennis Masters Series event in Hamburg and played at magnificent level at the French Open, only a brilliant Marcelo Rios could stop him at fourth round, but he established the bases for his future winning in 2002. Three further titles followed in 1999.