Tras unos años donde apenas había salido de Francia, en 2004 mejoró 200 posiciones en el ranking (desde la 386 hasta la 157) con un record de 18 victorias y 7 derrotas en los Challengers (títulos en Nottingham y Togliatti, y semifinal en Austin) y dos éxitos en torneos Promesas (Francia y España). Apareció en su primer campeonato ATP en Pekín y no pudo empezar con mejor pie, barrió al entonces número 5, Carlos Moyá, antes de caer en segunda ronda frente a Lee. En Noviembre, debutó en el ATP Masters Series en Paris, y se repitió el mismo papel que en China. Sorprendió a Ancic en la ronda de apertura para luego perder contra Cañas en segunda ronda. Aquí, sacó el tercer servicio más rápido del año en el circuito ATP, 232 kilómetros por hora.
En 2005 solo jugó ocho torneos. Estuvo lejos de las pista durante cinco meses desde noviembre 2004 hasta marzo 2005 a causa de una hernia discal. Más tarde, sufriría dos lesiones en el hombro derecho. Pero su calvario continuaría con problemas de espalda y en los abdominales desde Octubre hasta Febrero de 2006. Entre lesiones ganó un Challenger en Leon, derrotando a Weiner en Abril, no aprovechó una Wild Card para Roland Garros facilitando el paso a Andy Roddick y se impuso en un Promesas de Francia en Octubre, justo antes de sus dolencias.
Mejoró su ranking al año siguiente, a base de torneos promesas y de Challengers, a pesar de haber estado limitado por jugar solo ocho torneos debido a sus problemas físicos. Se perdió otros cuatro meses y medio desde Mayo hasta mediados de Septiembre. A partir de ahí, el francés consiguió un record de 19 victorias y 1 derrota en Promesas, conquistando tres títulos de cuatro finales. También venció en el Challenger de Rennes, y se clasificó para la final en Challenger de Lanzarote.
Fue el año pasado cuando el francés se colocó entre los 50 primeros por primera vez, tras una serie de consistentes resultados en ATP y un inmejorable juego en los Challengers, donde consiguió cuatro títulos y 24 victorias sobre 5 derrotas. Abrió el fuego en el Open de Australia en un intensísimo partido contra Andy Roddick en primera ronda. Como anécdota curiosa reseñar que se adjudicó el primer set después de un 20-18 eterno en el Tie Break más largo del Grande Aussie. A continuación, y después de arrasar contra las promesas de Francia, se mostró intratable, desde Abril hasta Junio, en los Challengers de Ciudad de México, Lanzarote, España y Surbiton, donde se impuso a Karlovic. Sobre hierba, destacable fue su victoria contra Hewitt en Queens y los Octavos de Final alcanzados en Wimbledon, torneo donde, antes de sucumbir frente a su compatriota Gasquet, pasó por encima de Lapentti, Benneteau y Feliciano López. Ya en el Open USA no estuvo nada mal su tercera ronda con triunfos sobre Hernández y Henman, pero Rafa Nadal se cruzó en su camino. Finiquitó la temporada con resultados importantes en su tierra. En concreto, las semifinales de Lyon donde eliminó al gran favorito, Richard Gasquet, vengándose de Wimbledon, y donde consiguió imponerse (junto con Grosjean) en la modalidad de dobles; y los Cuartos de Final de Metz cuyo verdugo fue Andy Murray. Gasquet se la devolvería más tarde en el Masters Series de París, en segunda ronda.