Current methods for reconstructing biological networks often learn either the topology of large networks or the kinetic parameters of smaller networks with a well-characterized topology. We have recently described a network reconstruction algorithm, the Inferelator 1.0, that given a set of genome-wide measurements as input, simultaneously learns both topology and kinetic-parameters. Specifically, it learns a system of ordinary differential equations (ODEs) that describe the rate of change in transcription of each gene or gene-cluster, as a function of environmental and transcription factors. In order to scale to large networks, in Inferelator 1.0 we have approximated the system of ODEs to be uncoupled, and have solved each ODE using a one-step finite difference approximation. Naturally, these approximations become crude as the simulated time-interval increases. Here we present, implement, and test a new Markov-Chain-Monte-Carlo (MCMC) dynamical modeling method, Inferelator 2.0, that works in tandem with Inferelator 1.0 and is designed to relax these approximations. We show results for the prokaryote Halobacterium that demonstrate a marked improvement in our predictive performance in modeling the regulatory dynamics of the system over longer time-scales.