Pierwszy kościół w Broku stanął prawdopodobnie w XI wieku. Po nim wzniesiono jeszcze kilka, również drewnianych. Budowę obecnego, rozpoczęto w 1542 roku, a poświęcenia dokonano po osiemnastu latach. Brok był w posiadaniu biskupów płockich, a że w tamtych czasach wznoszenie ko­ściołów i uposażenie parafii należało do właścicieli gruntów, dlatego aktualny kościół powstał staraniem biskupów Sa­muela Maciejewskiego i Andrzeja Noskowskiego. Kościół zaprojektował architekt biskupa Andrzeja Noskow­skiego, Jan Baptysta z Wenecji. Kaplicę północną w roku 1612 dobudował brokowski proboszcz, Jakub Odrzywołek Kapusta, a południową oraz kruchtę z zachodu wzniesiono w drugiej połowie XIX wieku. Kościół kilkakrotnie restaurowano, m.in. po zniszczeniach w okresie najazdów szwedzkich i po II wojnie światowej.

Na przykładzie kościoła w Broku świetnie widać, że na Mazowszu nowe prądy w sztuce pojawiały się później niż w innych częściach Polski. Chociaż w XVI w. powszechny był już styl renesansowy, świątynię w Broku charakteryzuje gotycka bryła - jedynie szczyty zwiastują zmiany w architekturze.
Nawa kościoła posiada sklepienie tunelowe, a kaplica i zakrystia kolebkowo-krzyżowe. Nasadę sklepienia stanowi dekoracyjna siatka sztukatorska z motywem liści połączonych listwami. Chór muzyczny, wsparty na trzech półkoliście zamkniętych arkadach, wykonano w XVIII wieku. W kościele znajdują się trzy ołtarze: główny św. Andrzeja Apostoła, Matki Boskiej Różańcowej w kształcie drzewa Jessego - po prawej stronie drzwi głównych, i św. Anny po lewej stronie. W 1969 roku podczas prac renowacyjnych, odkryto ślady polichromii z czasów bu­dowy kościoła, później pokrytej tynkiem. Przez kilka następnych lat polichromię odsła­niali i zabezpieczali konserwatorzy zabytków. Polichromie w kościele parafialnym p.w. św. Andrzeja Apostoła w Broku stanowią jeden z najbardziej znaczących przykładów monumentalnego malarstwa ściennego na Mazowszu w XVI wieku.