A QM/MM investigation is reported dealing with the nucleation and growth of small palladium clusters, up to Pd8, on the outer surface of a suitable model of boron nitride nanotubes (BNNTs). It is shown that BNNTs could have a template effect on the cluster growth, which is due to the interplay between Pd-N and Pd-Pd interactions as well as due to the matching of the B3N3 ring and the Pd(111) face arrangement. The values for the cluster adsorption energies reveal a relatively strong physisorption, which suggests that under particular conditions the BNNTs could be used as supports for the preparation of shape-controlled metal clusters.