W miejscu obecnej murowanej świątyni stał drewniany kościółek, o którym pierwsza wzmianka pochodzi z 1113 r. W roku 1331 drewnianą świątynię zastąpił kościół murowany wystawiony z fundacji książąt mazowieckich przez rycerza Andrzeja z Dinheim. Kościół został rozbudowany po 1551 r. przez arch. Jana Baptystę z Wenecji, znanego z budowy barbakanu na Starym Mieście w Warszawie oraz przebudowy bazyliki kolegiackiej w Pułtusku i kościoła w Broku nad Bugiem. Jego fundatorem był wojski warszawski Jan Brochowski herbu Prawdzic. Podczas „potopu szwedzkiego" kościół w Brochowie został poważnie uszkodzony, odbudował go w latach 1662-1665 właściciel wsi Olbracht Adrian Lasocki herbu Dołęga. Otoczono go murem z bastionami i fosą.
