The ability to tune the adsorption strength of the targeted gas on sensing materials is crucial for sensing applications. By employing first-principles calculations the adsorption and sensing properties of HCHO on small Pdn (n = 1–6) cluster decorated graphene have been systematically investigated. The adsorption energy is found to depend on the size of the Pdn cluster and can be tuned in a wide range from −0.68 eV on Pd(111) to −1.98 eV on the Pd3/graphene system. We also find that the Pdn/graphene (n = 5 and 6) systems have an appropriate adsorption energy for HCHO gas sensing. The current–voltage curves are calculated by the non-equilibrium Green's function method for the two-probe nano-sensor devices along both the armchair and zigzag directions. The devices constructed with Pdn/graphene (n = 5 and 6), having the highest absolute response over 20% at small voltages, should be applicable for HCHO detection. This work provides a theoretical basis for exploring potential applications of metal cluster decorated graphene for gas sensing.