De PvdA haalde bij de verkiezingen van 10 juni 2004 7 zetels in het Europees Parlement (EP). Lijsttrekker was Max van den Berg. Het verkiezingsprogramma was getiteld 'Een sterk en sociaal Europa'. De PvdA had voor de verkiezingen 6 zetels in het EP, maar toen had Nederland in totaal nog 31 zetels. Bij de verkiezingen van 2004 waren er 27 zetels in het EP te verdelen voor Nederland.
De PvdA haalde bij de verkiezingen voor het Europees Parlement van 10 juni 2004 1.124.549 (23,6%) van de 4.765.677 uitgebrachte stemmen. De partij haalde hiermee 7 zetels.
De PvdA nam aan de verkiezingen deel in een lijstencombinatie met GroenLinks. Deze combinatie verwierf 1 van de 5 te verdelen restzetels.
Om de voorkeursdrempel te halen waren 17.560,7 stemmen (10% van de kiesdeler) nodig. De nummer 8 op de kandidatenlijst, Emine Bozkurt, werd verkozen dankzij 24.359 voorkeursstemmen. Als zij niet zoveel voorkeursstemmen had gekregen, had niet zij maar Lily Jacobs (de nummer 7) een zetel in het Europees Parlement gekregen.