Aquesta església parroquial era situada en un raval a llevant del turó de la Suda. El caràcter menestral d’aquest barri facilità el seu ràpid creixement. És documentat des del 1154, en què s’esmenta el raval “dicitur Villanova, ad portam de Corbins”. La primera menció de l’església de Santa Maria Magdalena és de l’any 1163, en una donació feta per Pere del Talladell a favor d’un tal Joan de Santa Maria Magdalena. L’any 1168 hom sap que aquest Joan de Santa Maria havia de pagar un cens de 12 diners per habitar a l’església de Santa Maria Magdalena. Aquest mateix any l’església apareix relacionada en l’Ordinatio ecclesie Ilerdensis com a parròquia i cap d’una prepositura que integrava les esglésies de Sant Gili i Sant Pau del Mercadal.
Per un document de l’arxiu parroquial se sap que entre el 1434 i ja avançat el segle XVI es construí a l’església una nova volta gòtica. Probablement en aquest mateix període es bastí el cimbori que es pot observar en diferents gravats posteriors. Entre els segles XIII i XIV s’alçaren a l’església diverses capelles per iniciativa dels veïns, principalment personatges vinculats a la indústria i el comerç. Són diverses les deixes testamentàries per a l’obra del temple durant la primera meitat del segle XIII. A mitjan segle XIV, Eva Corneli, senyora d’Arbeca i emparentada amb els Cardona, instituí una capellania a l’església. La capella de Sant Joan fou instituïda pel ciutadà Ferrer d’Albesa al segle XIV, i la capella de Sant Nicolau pels Trullols, família d’industrial i mercaders. Al final del segle XV hi ha documentat el benefici de la capella de l’Assumpció. Molts dels beneficis que havien estat fundats a l’església parroquial de Sant Gili després de la guerra contra Joan II passaren a l’església de Santa Maria Magdalena.
L’any 1812, amb motiu de l’explosió del polvorí de la Suda durant la guerra del Francès, l’església resultà malmesa. Fou enderrocada pocs anys després, el 1838. Hi hagué la intenció de respectar la torre gòtica del campanar, però finalment també s’aterrà.