En 2001, el luxemburgués Gilles Muller hizo su debut en Copa Davis con el equipo de su país. Esa misma temporada, ganó el título de promesas de Kuwait, y el título de dobles junto a Scheidweiler, en el torneo de promesas de Luxemburgo.
En la temporada siguiente, en 2002, hizo su debut en un torneo ATP, fue el de Hertogenbosch, y perdió ante Heuberger en primera ronda. Ganó tres torneos de jóvenes promesas en Gran Bretaña, Jamaica y Brasil. Jugó en Copa Davis frente a Yugoslavia.
En 2003, jugó cayó en primera ronda del torneo ATP de Copenhague ante Lisnard. Jugó la Copa Davis ante Eslovaquia. Llegó a su primera final de Challenger, en Nápoles, pero perdió ante el francés Gasquet. Pero ganó el siguiente Challenger, primero en su carrera deportiva, en Valladolid ante Navarro Pastor.
Muller se convirtió en el primer jugador de su país en 2004, después de alcanzar el top 100 por primera vez. Ganó los Challengers de Nápoles y Córdoba ente Si Pasquele y Almagro, respectivamente. Su mejor actuación fue en Washington, donde llegó a la primera final de ATP de su carrera. Perdió ante Hewitt, después de haber ganado a Agassi en la final. También consiguió llegar a los cuartos de final de Shangai y Tokio.
En Copa Davis jugó ante Finlandia y Gran Bretaña. En dobles, ganó el Challenger de Andorra junto a Qureshi.
En 2005 firmó una gran temporada al terminar como número 59 del mundo. Llegó a tercera ronda del Masters Series de Indian Wells, tras caer ante Federer. En tierra batida, llegó a los cuartos de final de Casablanca, pero fue derrotado por el italiano Volandri.
En hierba, hizo su debut en Wimbledon, y llegó a tercera ronda, venciendo a Mantilla y a Nadal, pero cayendo finalmente ante el francés Gasquet. La segunda final de su carrera llegó en Los Ángeles, título que perdió ante Agassi. En el Open de Estados Unidos, fue derrotado por Roddick en la primera ronda.
Su última aparición de la temporada fue en el torneo de Bangkok, donde llegó a cuartos de final ante Federer. En dobles, llegó a las semifinales de los Challengers de Heilbronn y Córdoba.
Este zurdo de Luxemburgo alcanzó cuatro cuartos de final ATP mientras terminaba fuera del Top 100 por primera vez en tres años. Empezó la temporada alcanzando los cuartos de final en dos de los tres primeros torneos, perdiendo ante el campeón en ambos, en Chennai (perdió ante Ljubicic) y en Delray Beach (perdió ante Haas). Entre medias, alcanzó la segunda ronda del Open de Australia por primera vez (venció a Mello, perdió ante López). Consiguió un par de victorias en la Copa Davis contra Portugal. Alcanzó la final del Bermuda Challenger (perdió ante Vicente). Avanzó a cuartos de final en Estoril (perdió ante Davydenko). Sufrió cinco derrotas consecutivas en primera ronda antes de alcanzar los cuartos de final en Indianápolis (perdió ante Roddick). En la recta final del año, tuvo éxito en torneos Challenger. Alcanzó los cuartos de final en Bronx (perdió ante Udomchoke) y las semifinales en Grenoble (perdió ante Tourte). Alcanzó las semifinales en dobles en Casablanca (junto a Cristophe Rochus).
El nativo de Luxemburgo acumuló sus mejores resultados en torneos Challenger con dos semifinales.
Empezó la temporada llegando a la segunda ronda de Open de Australia, en la que perdió con Davydenko, y legó a cuartos en el Durban Challenger.
En febrero, llegó a semifinales del Besancon Challenger. Se clasificó para Wimbledon, donde ganó a Hernández pero perdió frente a Juan Carlos Ferrero en cuatro sets.
No ganó dos partidos consecutivos de nuevo hasta finales de julio, llegando a las semifinales del Recanati Challenger. Siguió con tres cuartos de final en Segovia, Estambul y Orleáns Challenger.
En octubre, cerró la temporada siendo finalista en Rennes y Holding y llegando a semifinales en Seúl.