NMR well logging is a popular tool in the petroleum industry to estimate porosity, specific surface area, and permeability of porous media. In this study, a random walk algorithm is used to simulate the NMR response of porous, water-saturated media, which, in turn, probes the relation between microstructure and transport. The serial implementation of the random walk algorithm is computationally very intensive for large porous samples. A parallel random walk code is developed using Message Passing Interface (MPI) in Fortran. Various domain decomposition techniques are implemented. The walker distribution across processors without domain decomposition gives the best speedup. The domain decomposition with overlapped layers requires smaller processor memory. Increasing the overlap between adjacent domains lowers the interprocessor communication and leads to improved speedup. For the given parameters, an overlap of two layers was found to be optimal. Domain decomposition along the z direction was found to be more effective than decomposition along either the x or y direction. By using the parallel random walk code, we are able to solve a 256x256x256 voxel system in less than 8 h using 32 processors on an IBM SP2 machine.