We present sequential and parallel Monte Carlo algorithms for computing the solvent accessible surface area of protein molecules. The basic idea underlying our algorithms is to generate points uniformly at random on the surface of spheres obtained by increasing the van der Waals’ radii of the atoms with the van der Waals’ radius of the solvent molecule and to test the points for accessibility. We also present an efficient algorithm to compute sphere intersections more efficiently using domain specific knowledge. The expected running time of our sequential algorithm is O(n+s), where n is the number of atoms in the protein and s is the number of points generated. We also provide error bounds as a function of the sample size. Our parallel algorithm can use O(n) processors and provides linear speedup. Computing sphere intersections is common to the various approaches for solving this problem and our algorithm to compute the intersections can be used by them. It takes only O(n) sequential time, which compares favorably with existing algorithms that take O(n 2) worst-case time.