2000 was another Olympic year and once again NBAC swimmers competed at Olympic Trials. Michael Phelps became the youngest male swimmer in 68 years to make a US Olympic Team. Michael finished second in 200 Butterfly to make the US squad. NBAC Senior Coach Bob Bowman accompanied Michael to Sydney, Australia where he finished fifth in 200 Butterfly. Michael Phelps' relentless assault on the National Age Group Records led to NBAC passing a milestone of having had its swimmers set over 100 of these records. Coaches Paul Yetter and Rachel Fishbain joined the staff in 2001.

In March of 2001, at age fifteen, Michael Phelps broke the World Record in 200 Butterfly becoming the youngest male world record holder in history. NBAC Senior coach Bob Bowman was named as assistant US National Team Coach for the World Championships. Michael lowered his own World Record at the FINA World Championships in Fukuoka, Japan in July, winning a gold medal in 200 Butterfly. In August, Michael won 200 IM and 100 Butterfly at U.S. National Championships in Fresno, California. He was the male high point award winner of the meet. Meghan Sackett, 14, finished third in 1500 Free winning the Female Rookie of the Meet award. Bob Bowman received both the ASCA and the USA Swimming Coach of the year honors.

2002 brought some new faces to the coaching staff while marking a new club milestone. Coaches Tom Yetter and Dan Dougher joined the staff as Paul Yetter took the lead coaching position in Harford County. Bob and Michael traveled to Yokohama, Japan for the Pan Pacific Games where Michael won four gold and two silver medals. Michael Phelps became NBAC's first multiple world record holder in Individual events when he broke the 400 IM record at Summer Nationals in Ft. Lauderdale. In a race considered by many to be one of the best races ever, Michael edged out Eric Vendt to take the record. Also at Nationals, Jamie Barone was named Rookie of the Meet. Bob Bowman was named USA Swimming Developmental Coach of the Year. NBAC was named a 2002 USA Swimming Gold Club, one of only 25 in the country.

2003 began on a high note with NBAC retaining its title as Eastern Classic Champions in Atlanta, Georgia. In March, NBAC Harford standout twelve-year-old Courtney Kalisz set three National Age Group Records on Sunday at the Eastern Zone Region II Sectionals. In May, she continued her assault with six 11-12 national age group records in Ann Arbor, Michigan. Between those record setting swims, Michael Phelps and Emily Goetsch competed for Team USA in the Mutual of Omaha Duel in the Pool between the United States and Australia. Emily finished fourth in 100 M Fly and Michael won three individual events and one relay. He broke his own world record in 400 IM and set a new American Record in 100 Fly. This just days after Michael had won national titles in 100 Fly, 200 Free and 200 Backstroke, becoming the first man to win titles in three strokes at a National Championship.

The Summer of 2003 saw Phelps on a tear unrivalled in the history of competitive swimming. In a span of two months, he broke the world records in the 200 IM four times, lowered his own 200 Fly and 400 IM records and broke the world record in 100 Butterfly. He left the World Championships in Barcelona with four gold and two silver medals. Shortly thereafter, Michael became the first man to win five national titles at Senior Nationals in College Park, Maryland where he won an unprecedented five national titles in 100, 200 (American Record) and 400 Free, 200 Back, and 200 IM, in which he broke his own world record. Emily Goetsch won her first national title in the 100 M Butterfly. NBAC was again named a USA Swimming Gold Club.