We present a new international migration model that combines stochastic sampling techniques with dynamic accounting of flows by means of evolution equations. Migration flows are sampled from paramaterized probability distributions based on reported migration flow data that is partitioned by socio-economic covariates. This method allows for non-trivial time evolution that goes beyond extrapolation, while requiring minimal prior knowledge about the elusive processes driving migration flows. It thus combines the advantages of different existing modeling approaches. In hindcasts our model compares well with bilateral migrant stock data in many world regions and country income groups. Moreover, we observe a significant difference between the full model and its deterministic formulation, which highlights the non-Gaussian and interdependent nature of migration flow distributions and corroborates the use of a stochastic approach. Our model can be flexibly extended with additional information, e.g. regional migration policies, which are expected to further improve the agreement with data.