Environmental pollution caused by the presence of aromatic aldehydes and dyes in wastewater is a serious global concern. An effective strategy for the removal of these pollutants is their catalytic conversion, possibly to valuable compounds. Therefore, the design of efficient, stable and long-lifetime catalysts is a worthwhile research goal. Herein, we used nanofibrous carbon microspheres (NCM) derived from the carbohydrate chitin present in seafood waste, and characterized by interconnected nanofibrous networks and N/O-containing groups, as carriers for the manufacture of a highly dispersed, efficient and stable Pd nano-catalyst (mean diameter ca. 2.52 nm). Importantly, the carbonised chitin’s graphitized structure, defect presence and large surface area could promote the transport of electrons between NCM and Pd, thereby endowing NCM supported Pd catalyst with high catalytic activity. The NCM supported Pd catalyst was employed in the degradation of some representative dyes and the chemoselective hydrogenation of aromatic aldehydes; this species exhibited excellent catalytic activity and stability, as well as applicability to a broad range of aromatic aldehydes, suggesting its potential use in green industrial catalysis.