Năm 2004 tại Athena, Phelps được kỳ vọng sẽ phá kỷ lục 7 huy chương vàng môn bơi lội do huyền thoại đồng hương Mark Spitz thiết lập năm 1972. Tuy san bằng thành tích 4 huy chương vàng cá nhân của Spitz (ở các nội 100 và 200 m bướm, 200 và 400 m cá nhân hỗn hợp) nhưng Phelps chỉ giành được 2 huy chương đồng tại các nội dung 4 x 100 m tiếp sức tự do và 200 m tự do vì vậy kỷ lục do Spitz giữ suốt 32 năm vẫn tiếp tục đứng vững. Dù sao thì với thành tích 6 vàng, 2 đồng, Phelps cũng đã san bằng kỷ lục về số huy chương do một cá nhân đạt được trong một kỳ Thế vận hội (do vận động viên thể dục Alexander Dityatin thiết lập năm 1980 ở Moskva).