An apparatus and method are described for low overhead synchronous page table updates. For example, one embodiment of a processor comprises: a set of one or more cores to execute instructions and process data; a translation lookaside buffer (TLB) comprising a plurality of entries to cache virtual-to-physical address translations usable by the set of one or more cores when executing the instructions; locking circuitry to allow a thread to lock a first page table entry (PTE) in the TLB to ensure that only one thread can modify the first PTE at a time, wherein the TLB is to modify the first PTE upon the thread acquiring the lock; a PTE invalidation circuit to execute a PTE invalidate instruction on a first core to invalidate the first PTE in other TLBs of other cores, the PTE invalidation circuit, responsive to execution of the PTE invalidate instruction, to responsively determine a number of other TLBs of other cores which need to be notified of the PTE invalidation, transmit PTE invalidate messages to the other TLBs, and wait for responses; and the locking circuitry to release the lock on the first PTE responsive to receiving responses from all of the other TLBs.