A new Pd catalyst chemically bonded to cellulose nanocrystals surfaces (CNC-BIA-Pd) was developed. 2-(1H-Benzo[d]imidazol-2-yl) aniline (BIA), tosylated cellulose nanocrystals (CNC-TOS) and PdCl2 were the reactants for the synthesis of the new catalyst designed to be used for the Ullmann reaction. The modified cellulose nano catalyst was characterized with various analytical tools. The catalyst had excellent selectivity and activity in a short reaction time (45 min) and outstanding TON (490) and TOF (1960) values. The nano catalyst was determined to be reusable for at least eight cycles. The CNC-BIA-Pd catalyst indicated excellent catalytic efficiency for the Ullmann C–O reaction when it was compared to commercial palladium catalysts. A new Pd catalyst chemically bonded to cellulose nanocrystal surfaces (CNC-BIA-Pd) was developed and used for the Ullmann reactions. The catalyst had excellent selectivity and activity in a short reaction time and outstanding TON (490) and TOF (1960) values. The nano catalyst was determined to be reusable for at least eight cycles.