This paper addresses implementation of digital IIR filters using stochastic computing. Stochastic computing requires fewer logic gates and is inherently fault-tolerant. Thus, these structures are well suited for nanoscale CMOS technologies. While it is easy to realize FIR filters using stochastic computing, implementation of IIR digital filters is non-trivial. Stochastic logic assumes independence of input signals; however, feedback in IIR digital filters leads to correlation of input signals, and the independence assumption is violated. This paper demonstrates that, despite feedback in IIR filters, these filters can be implemented using stochastic logic. The key to stochastic implementation is selection of an IIR filter structure where the states are orthogonal and are, therefore, uncorrelated. Two categories of architectures are presented for stochastic IIR digital filters. One category is based on the basic lattice filter representation where the states are orthogonal, and the other is based on the normalized lattice filter representation where states are orthonormal. For each category, three stochastic implementations are introduced. The first is based on a state-space description of the IIR filter derived from the lattice filter structure. The second is based on transforming the lattice IIR digital filter into an equivalent form that can exploit the novel scaling approach developed for inner product computations. The third is optimized stochastic implementation with reduced number of binary multipliers. Simulation results demonstrate high signal-to-error ratio and fault tolerance in these structures. Furthermore, hardware synthesis results show that these filter structures require lower hardware area and power compared to two's complement realizations.