Desde sus inicios en el mundo del tenis, Pavel apuntó una proyección excelente, no en vano venció en el torneo junior de Roland Garros y alcanzó las semifinales en Wimbledon.
Profesional desde 1990, aunque sus primeros éxitos deportivos comenzaron a llegar en 1996, año en el que disputó los Juegos Olímpicos de Atlanta, además de alcanzar las semifinales en el campeonato ATP de Bucarest.
En la temporada siguiente, volvió a disputar la penúltima ronda del trofeo de Chennai y 1998 logró su primera victoria de su carrera deportiva al conseguir adjudicarse el torneo de Tokio en categoría individual y el de Bucarest en la modalidad de dobles. Era la primera vez que un jugador rumano se hacía con un título oficial de la ATP desde 1978.
En 1999, Pavel volvió a saborear la victoria, al ganar en el Challenger de Vence y, en dobles, disputó las finales de Munich y Hertogenbosch. En 2000, el principal hito del tenista rumano fue la victoria en el campeonato de Saint Poelten y, en la siguiente campaña, el rumano se adjudicó el AMS de Montreal.
En 2002, Andrei Pavel llegó, por primera vez en su carrera, a disputar los cuartos de final en un Grand Slam, concretamente en Roland Garros, aunque el español Alex Corretja se cruzó en su camino.
Al año siguiente, el tenista rumano consiguió mantener el nivel de juego permaneciendo en el Top 100 por sexta temporada consecutiva, no obstante en 2003, Pavel tuvo problemas físicos perdiéndose seis meses de competición.
En 2004, el jugador de Constanza completó su mejor temporada hasta el momento, logrando ingresar en el Top 20 de la ATP, llegando en octubre de ese año a ocupar la decimotercera posición de la prestigiosa lista. Venció en el Challenger de Ucrania y disputó la penúltima ronda en Houston.
En 2005, Pavel abrió la temporada alcanzando los cuartos de final en el Abierto de Australia y disputó las semifinales de la Copa Davis, cayendo ante Croacia, país que a la postre fue el vencedor del prestigioso torneo.
En 2006 el número uno de Rumanía acabó fuera del Top 100 por primera vez desde 1997. Alcanzó la segunda ronda en el Abierto de Australia. Ya en febrero, venció a Roddick en un partido a cinco sets en la eliminatoria de primera ronda de Copa Davis. A continuación perdió seis encuentros consecutivos antes de avanzar hasta la final del torneo de Poertschach, que perdió ante Davydenko. Superó a Wawrinka y Mirnyi para alcanzar los cuartos de final en Gstaad. En el US Open, ganó el primer set a Agassi en el primer partido, pero acabó sucumbiendo ante el americano. En Bucarest, sólo superó una ronda (ante Pashanski) y luego perdió con Moyá. A finales de septiembre tuvo que disputar la eliminatoria por la permanencia en el Grupo Mundial de la Davis con Rumanía ante Corea. Ganó los dos individuales y también el dobles. Su temporada concluyó con otra primera ronda en Palermo y una segunda en San Pertersburgo tras superar a Mirnyi.
Formó pareja con varios compañeros para vencer en los torneos de Auckland, Munich y Gstaad, además de firmar las semifinales de Roland Garros, donde cayó frente a los Bryan.
El número uno rumano acabó número cien por novena vez en los últimos diez años. Llegó a finalista del torneo de Túnez.
En julio, disputó su mejor torneo de la temporada en Umag donde derrotó al número 12, Ljubicic, en la primera ronda y al número 25, Volandri, en cuartos, antes de perder frente a Carlos Moyá en la final.
Después mejoró su posición, avanzando del número 132 al 103.
Ayudó a su país natal a entrar de nuevo en 2008 en el Grupo Mundial de Copa Davis ganando ambos de sus partidos individuales contra los japoneses Soeda, en cuatro sets, y Takao Suzuki, en cinco sets.
En octubre, llegó a semifinales del Mons Challenger, donde fue derrotado por Vliegen.