The Coulomb blockade across Fe and Pd nanoislands grown on single-crystalline MgO insulator films on Fe(001) was investigated with scanning tunneling microscopy. In I(U) spectra of individual islands, the characteristic steps of the Coulomb staircase were observed as a function of island size. A detailed analysis of the Coulomb staircase energetics in terms of the island capacitance reveals the expected linear behavior for electrostatic interactions. For ferromagnetic Fe islands, however, a significant offset of 1 eV was found, which is missing in the case of nonmagnetic Pd islands. This effect is explained by the spin dependence of the electronic transport across the MgO barrier in combination with a quasihalf-metallic density of states of the Fe islands, as corroborated by first-principles electronic-structure calculations.