La Chiesa dedicata a Maria SS Immacolata è centro di aggregazione della comunità, elemento caratterizzante il borgo assieme alla Piazza intitolata al Milite Ignoto. Come un corpo unico, tracciano i confini della strada principale che attraversa Palombaio, in direzione Est (Bitonto) e Ovest (Mariotto).
La chiesa costruita nei primi anni cinquanta del XIX secolo, fu eretta a parrocchia nel 1859 per assicurare il servizio pastorale agli abitanti del borgo.
Fu consacrata dal vescovo Vincenzo Mattarozzi e fu intitolata all’Immacolata Concezione a cui è devota anche la stessa Bitonto. La Chiesa diviene pertanto insieme sinonimo di pieno riconoscimento delle dignità di borgo urbano a Palombaio e passaggio alla fase di modernità e crescita demografica della comunità.
Fu costruita, con impianto a mononavata, sul progetto dell’architetto Masotino, celebre urbanista dell’epoca, tra il 1850 e 1854. Una ventina d’anni più tardi venne realizzata una statua lignea della Vergine Immacolata dal celebre scultore di scuola napoletana Enrico Pedace: realizzata con grande maestria, raffigura la Vergine in una posa plastica che richiama la purezza assoluta sancita dal Dogma Pontificio.