In this paper we propose a numerical scheme for a class of backward stochastic differential equations (BSDEs) with possible path-dependent terminal values. We prove that our scheme converges in the strong L2 sense and derive its rate of convergence. As an intermediate step we prove an L2-type regularity of the solution to such BSDEs. Such a notion of regularity, which can be thought of as the modulus of continuity of the paths in an L2 sense, is new. Some other features of our scheme include the following: (i) both components of the solution are approximated by step processes (i.e., piecewise constant processes); (ii) the regularity requirements on the coefficients are practically "minimum"; (iii) the dimension of the integrals involved in the approximation is independent of the partition size.