There is great interest in elucidating the cluster structure of brain networks in terms of modules, blocks or clusters of similar nodes. However, it is currently challenging to handle data on multiple subjects since most of the existing methods are applicable only on a subject-by-subject basis or for analysis of a group average network. The main limitation of per-subject models is that there is no obvious way to combine the results for group comparisons, and of group-averaged models that they do not reflect the variability between subjects. Here, we propose two novel extensions of the classical Stochastic Blockmodel (SBM) that use a mixture model to estimate blocks or clusters of connected nodes, combined with a regression model to capture the effects on cluster structure of individual differences on subject-level covariates. Multi-subject Stochastic Blockmodels (MS-SBM) can flexibly account for between-subject variability in terms of a homogenous or heterogeneous effect on connectivity of covariates such as age or diagnostic status. Using synthetic data, representing a range of block sizes and cluster structures, we investigate the accuracy of the estimated MS-SBM parameters as well as the validity of inference procedures based on Wald, likelihood ratio and Monte Carlo permutation tests. We show that multi-subject SBMs recover the true cluster structure of synthetic networks more accurately and adaptively than standard methods for modular decomposition. Permutation tests of MS-SBM parameters were more robustly valid for statistical inference and Type I error control than tests based on standard asymptotic assumptions. Applied to analysis of multi-subject resting state fMRI networks (13 healthy volunteers; 12 people with schizophrenia; N = 268 brain regions), we show that the Heterogeneous Stochastic Blockmodel estimates "core-on-modules" architecture. The intra-block and inter-block connection weights vary between individual participants and can be modelled as a logistic function of subject-level covariates like age or diagnostic status. Multi-subject Stochastic Blockmodels are likely to be useful tools for statistical analysis of individual differences in human brain graphs and other networks whose prior cluster structure needs to be estimated from the data.