Parafia w Postoliskach jest jedną z najstarszych (obok Kobyłki i Klembowa) parafii w powiecie wołomińskim, a zarazem najstarszą w gminie Tłuszcz. Powstała w XVI w., kiedy to właścicielem tutejszej wioski pełniącej funkcję osady targowej był Andrzej Postolski. Dokładna data założenia parafii nie jest znana. W 1540 r. erygował ją ponownie biskup płocki Jan Buczacki. Właśnie w tym czasie zbudowano drewniany kościół ufundowany przez kanonika wileńskiego i pułtuskiego Stanisława Dąbrowskiego. Podczas „potopu” szwedzkiego kościół został zniszczony. Na jego miejsce, w 1699 r., wzniesiono świątynię, która przetrwała aż do 1920. Budynek rozebrano, ponieważ w latach 1913–1919 powstał obecny neogotycki kościół. Jego budowniczym, według projektu Hugona Kudery, był ks. Wacław Koskowski.
Neogotycka świątynia w Postoliskach jest trójnawową bazyliką o czworobocznej podstawie. Boczne ołtarze pochodzą z XVIII w. W jednym z nich znajduje się obraz Serce Jezusa A. Kowalskiego z 1921 r. W drugim – obraz Trójca Święta nieznanego autora z XVIII w. Kolejnym płótnem, na które warto zwrócić uwagę jest Anioł na cmentarzu, przypisywany zwykle błędnie Miłoszowi Kotarbińskiemu. Naprawdę namalował go jego kuzyn – Wilhelm Kotarbiński. W kościele można znaleźć więcej cennych zabytków, takich jak siedemnastowieczny konfesjonał, krucyfiksy i monstrancje.
W trakcie II Wojny Światowej, w marcu 1942 r. przy kościele w Postoliskach lądowali trzej spadochroniarze – polscy cichociemni. Mieli trafić do Nowej Wsi pod Wołominem, gdzie czekali na nich oficerowie AK. Plany pokrzyżowali Niemcy. Żołnierze podziemia nie zdołali nadać umówionego sygnału. Właśnie to lądowanie upamiętnia pomnik stojący w samym centrum miejscowości.
Kościół został wpisany do rejestru zabytków Narodowego Instytutu Dziedzictwa (nr rej.: A-1049 z 20.12.2011).