The utilization of perfluoro-tagged palladium nanoparticles immobilized on fluorous silica gel through fluorous–fluorous interactions (Pdnp-A/FSG) or linked to silica gel by covalent bonds (Pdnp-B) in the alkynylation of terminal alkynes with aryl halides under aerobic, copper- and phosphine-free conditions in water, and their recovery and re-utilization, is described.