La prima data certa nella costruzione di una chiesa a Melegnano è il 1398 in quanto essa viene già citata nella Notitia Cleri Mediolanensis e nell'ottobre del 1418 apprendiamo che papa Martino V, in visita a Milano, concesse una speciale indulgenza per promuovere il restauro della chiesa che aveva saputo essere in condizioni disastrose. Il 6 luglio 1442, venne creata la pieve di Melegnano e la chiesa locale venne eletta a collegiata prepositurale, affrancandola dalla ben più antica pieve di San Giuliano Milanese. La chiesa, dall'epoca di Martino V, era ormai stata completamente riedificata e nel 1506 sappiamo della sua dedicazione alla Natività di San Giovanni Battista. Per questa speciale occasione, la chiesa melegnanese commissionò al Bergognone una splendida pala d'altare su tavola, firmata e datata dall'artista milanese, ancora oggi visibile all'interno della chiesa, che rappresenta Il battesimo di Cristo.
Esternamente, la chiesa si presenta con la facciata in mattoni e la struttura a salienti, mentre internamente l'aula è suddivisa in tre navate ad impianto basilicale; a completare la struttura si trova una cupola che si raccorda al presbiterio grazie a delle vele di forma triangolare e con un tiburio cilindrico. Il campanile, eretto nel 1482, venne sopraelevato nel XVII secolo. L'altare maggiore venne rifatto completamente nel 1635, assieme ad altri due altari laterali nelle cappelle.