A large variance exists in the amplitude of the Stellar Mass - Halo Mass (SMHM) relation for group and cluster-size halos. Using a sample of 254 clusters, we show that the magnitude gap between the brightest central galaxy (BCG) and its second or fourth brightest neighbor accounts for a significant portion of this variance. We find that at fixed halo mass, galaxy clusters with a higher magnitude gap have a higher BCG stellar mass. This relationship is also observed in semi-analytic representations of low-redshift galaxy clusters in simulations. This SMHM-magnitude gap stratification likely results from BCG growth via hierarchical mergers and may link assembly of the halo with the growth of the BCG. Using a Bayesian model, we quantify the importance of the magnitude gap in the SMHM relation using a multiplicative stretch factor, which we find to be significantly non-zero. The inclusion of the magnitude gap in the SMHM relation results in a large reduction in the inferred intrinsic scatter in the BCG stellar mass at fixed halo mass. We discuss the ramifications of this result in the context of galaxy formation models of centrals in group and cluster-sized halos.