We present a perfect sampling algorithm that can be applied to the master equation of gene regulatory networks. The method recasts Gillespie’s stochastic simulation algorithm (SSA) in the light of Markov chain Monte Carlo methods and combines it with the dominated coupling from the past (DCFTP) algorithm to provide guaranteed sampling from the stationary distribution. We show how the DCFTP-SSA can be generically applied to genetic networks with feedback formed by the interconnection of linear enzymatic reactions and nonlinear Monod-and Hill-type elements. We establish rigorous bounds on the error and convergence of the DCFTP-SSA, as compared to the standard SSA, through a set of increasingly complex examples. Once the building blocks for gene regulatory networks have been introduced, the algorithm is applied to study properly averaged dynamic properties of two experimentally relevant genetic networks: the toggle switch, a two-dimensional bistable system; and the repressilator, a six-dimensional transcriptional oscillator.