El setembre del 2004, en vistes a les eleccions del 2005, l'EDUP es va unir al Partit Democràtic Medhin d'Etiòpia (Ethiopian Medhin Democratic Party), conegut com a Mehdin o Partit Mehdin, i va agafar el nom de Partit d'Unió Democràtic Etiòpic - Mehdin formant una aliança electoral amb tres altres partits anomenada Coalició per la Unitat i la Democràcia (CUD o Kinijit) que a les eleccions del 15 de maig de 2005 ja havia aconseguit 108 escons quan el govern va ordenar suspendre el recompte al·legant frau; en els resultats final retocats només es van atorgar a l'aliança 34 escons perquè una part dels parlamentaris va refusar prendre possessió dels escons. L'octubre de 2005 el comitè central va decidir abandonar la CUD. Ato Lidetu Ayalew fou el president i Wezero Sophia Yilma el vicepresident.[1] Lidetu Ayalew fou objecte d'una forta campanya de difamació per part de la resta de la CUD. Els resultats de les eleccions del 2010 van mostrar no obstant que els problemes de la CUD no estaven només en el EDUP-M[2]
A les eleccions parcials del 2008 els dos partits ja s'havien separat i el Partit d'Unió Democràtic Etiòpic va agafar el nom de Partit Democràtic Etiòpic i el Mehdin recuperava el de Ethiopian Medhin Democratic Party.
