Structure, stability, dynamics, and the electronic structure of small sodium clusters with 2 to 12 atoms adsorbed on the NaCl(001) surface are studied using an ab initio total energy method. The interaction between the ideal surface and the metal cluster is found to be weak due to a large energy gap between the surface and the cluster single-electron states. As a result, the geometry and the electronic structure of the smallest clusters (N less than or equal to 6) is distorted only slightly if compared to the free clusters. For larger sizes it seems possible to have both 2D and 3D structure isomers with a notable interisomeric energy barrier. The cluster binding energy to the surface has a local maximum at N=6 which we interpret to be caused by electronic shell effects in 2D. The weak cluster-surface interactions are modified dramatically in the presence of surface F centers (missing chlorine atoms). The F center increases the adsorption energy of sodium adatom by 1 eV and changes the nature of adsorption from physisorption to chemisorption. Similarly, the binding of small sodium clusters to the surface is enhanced-by F centers.