国防軍退官後の1996年には、ベンヤミン・ネタニヤフの要請を受け、政界への進出を決意。同年実施の総選挙で右派政党・リクードの目玉候補として擁立され当選を果たし、同時実施の首相選で勝利を収めたネタニヤフの下で国防相をつとめる。しかしながら、モルデハイはリクード内ではハト派に属し、対アラブ・パレスチナ融和論者であるため、党内強硬派を代表するネタニヤフとは齟齬があり、対立関係が先鋭化、99年1月には新党結成の動きを露にし、総選挙の候補者登録に応じなかったことにネタニヤフが激怒、同月23日にネタニヤフはモルデハイの更迭に踏み切り、記者会見の際にはモルデハイを激しい口調で糾弾した。国防相更迭後は、リクードを離党し、ネタニヤフとの対立から同じようにリクードを離党していたダン・メリドール財務相(メリドールは現在はネタニヤフと和解・復党を果たしている)らと2月23日に中道新党・中道党を結成し、一時モルデハイは、ネタニヤフ、エフード・バラック労働党党首に次ぐ20%の支持を集めるものの(同年2月の、イデェオト・アハロノト紙・世論調査)、最終的には4.6%と低迷、首相選からの撤退を余儀なくされ、議会選でも6議席と低迷した。