Youzhny ganó cuatro títulos de promesas en 1999 y subió 700 posiciones. Un año después debutó en la Copa Davis ante Bélgica, y además, ganó su primer Challenger en Samarcanda. Sus primeros cuartos de final de un torneo ATP los logró en Moscú.
Finalizó la temporada 2001 dentro de los cien primeros. Llegó hasta la tercera ronda del Open de Australia y a semifinales en Copenhague. Su mejor resultado en Grand Slam fueron los cuartos de final de Wimbledon, tras perder ante Rafter. También consiguió alcanzar la tercera ronda en el Open de Estados Unidos, pero se topó con Sampras.
Su primer título ATP lo consiguió en Stuttgart ante Cañas. En ese mismo año, ayudó a Rusia a alzarse con la Copa Davis al ganar su partido contra el francés Mathieu. Se perdió los torneos veraniegos de Estados Unidos por una lesión en la espalda. En la recta final de la temporada, perdió la final de San Petersburgo ante Grosjean.
Finalizó en el top 50 en 2003, llegando a tres semifinales ATP, las de Doha, Halle y Lyon. En el Open de Australia, Roddick le batió en cuartos. Sus mejores resultados en tierra batida fueron en Munich, Bastad y Stuttgart.
Su mejor temporada hasta el momento la completó en 2004, la finalizar en el top 20 por primera vez. Ganó el segundo título ATP de su carrera en San Petersburgo ante Beck. Fish le eliminó de los cuartos de final de los Juegos Olímpicos de Atenas.
En el Open de Estados Unidos, llegó hasta la tercera manga. Perdió la final de Beijing ante su compatriota Marat Safin. Cerró la temporada con los cuartos de final de Lyon, las semifinales de Moscú y los cuartos de Masters De París.
La línea ascendente de su carrera se estancó un poco en 2005, puesto que bajó hasta el top 50 del ranking. Llegó a la cuarta ronda de Wimbledon. Llegó a cuartos de final en Bastad y Kitzbuhel, mismo resultado que consiguió en el Masters de Cincinnati, tras perder ante Roddick. Malisse le apeó de la tercera ronda del Open de Estados Unidos. Terminó la temporada alcanzando los cuartos de final de Beijing, Moscú y San Petersburgo. También jugó con Rusia la primera manga de la Copa Davis.
El número 3 ruso, por detrás de Davydenko y Tursunov, acabó la temporada entre los 25 mejores tenistas por segunda vez en tres años, destacando por llegar por primera vez a las semifinales de un Grand Slam. Completó una buena marca en los primeros siete meses del año, llegando a dos semifinales y a dos cuartos de final.
Se metió en cuartos de final en el torneo de apertura de Doha, cayendo ante Haas, a la misma ronda en Zagreb, donde le derrotó el campeón Ljubicic, y a semifinales en Dubai siendo derrotado por Federer.
Youznhy llegó hasta la tercera ronda en Wimbledon donde fue eliminado por Djokovic. Su mejor actuación en tierra batida la llevo a cabo al meterse en semifinales en Kitzbuhel, torneo en el que fue eliminado por Chela. Pero su mejor actuación del año llegaría en el Open USA donde llegó como número 54 del ranking tras derrotar a Hrbaty, Massu y al trío español formado por el número 13 Ferrer, el número 5 Robredo y al número 2 Nadal para caer ante Roddick en cuatro sets en las semifinales. Esto le permitió subir hasta el puesto número 24.
Fue seleccionado para disputar las semifinales de la Copa Davis ante Estados Unidos y consiguió un triunfo en cuatro sets ante el número 9 Blake, lo que le dio la victoria a Rusia una ventaja de 2-0.
El 25 de octubre se rompió los ligamentos de su tobillo derecho jugando un partido de dobles en Sant Petersburgo. En esta temporada estableció una marca de victorias y derrotas de 3-6 ante oponentes del Top 10 y un registro de 13-10 en pista dura, 6-7 en tierra batida, 4-2 en moqueta y 2-2 en hierba.
El número 2 ruso, por detrás de Davydenko, terminó entre los 20 mejores tenistas en 2007 por primera vez en tres años. Irrumpió en el Top 10 el 13 de agosto y se mantuvo allí una semana. Consiguió una marca de victorias y derrotas de 18-5 en los dos primeros meses del año y logró el tercer título ATP de su carrera en Rótterdam donde derrotó a Ferrer, Djokovic y Ljubicic. Fue finalista en Dubai, enfrentándose a los dos mejores tenistas del mundo, pero tras derrotar a Nadal en cuartos perdió en la final ante Federer. Se metió en semifinales de Zagreb, cuartos en Doha y en Marsella, donde perdió ante Ljubicic, en las dos primeras, y Badhdatis en la última.
En mayo llegó a la final de Munich pero la perdió ante Kohlschreiber y fue eliminado por Federer en la cuarta ronda de Roland Garros.
En hierba, alcanzó los cuartos en Halle y la cuarta ronda en Wimbledon, cayendo ante Berdych y Nadal respectivamente. Regresó a la tierra batida en julio y fue semifinalista en Amersfoort, eliminado por Darcis.
Tras caer en la segunda ronda del Open USA ante Kohlschreiber, ganó un partido crucial de Copa Davis en individuales ante Petzschner, lo que permitió a Rusia ganar por 3-2 y alcanzar la final por segundo año consecutivo. Cerró la temporada llegando a semifinales en Sant Petersburgo y a cuartos en el Master de Paris, siendo eliminado por Murray en el primero y por Nadal en el segundo. En este último derrotó al número 9 González y al número 10 Haas.
Terminó el año con un registro de victorias y derrotas de 24-12 en pista dura, 15-8 en tierra batida, 6-2 en moqueta y 5-1 en hierba. En dobles, ganó el título en Doha, junto a Zimonjic, y en Munich junto a Kohlschreiber. Sobrepasó el millón de dólares de ganancias en una temporada por primera vez en su carrera.