In this paper, a stochastic version of the classical deterministic balanced single commodity capacitated transportation network problem is presented. In this model, each arc of the network connects a supply node to a demand node and the flow of units forming along each arc of the network forms a stochastic process (i.e., G/M/1 queueing system with generally distributed interarrival time, a Markovian server, a single server, infinite capacity, and the first come first served queueing discipline). In this model, the total transportation cost is minimized such that the total supply rate is equal to the total demand rate, and the resulting probability of finding excessive congestion along each arc (i.e., the resulting probability of finding congestion inside the queueing system formed along each arc in excess of a fixed number) is equal to a desirable value. This paper is a generalization of Pourbabai’s model who presented the Markovian version of this model where the flow of units along each arc connecting a supply node to a demand node was modeled by a simple M/M/1 single server Markovian queueing process.