It is well-known that the computa- tion of the permanent of 0-1 matrices, which is the same as computing the number of matchings in bipartite graph, is #P-complete. However the complexity of computing a good approximation of the number of matchings, is an open question and it is the leading candidate for a problem for which one solution can be found in polynomial time, but for which even approximating the number of solu- tions is hard. In this paper we present a fully poly- nomial (e, 6)-approximation scheme for the per- manent of 0-1 matrices where at least half of the entries in every row and every column are l's. The novel algorithm uses a Markov chain that con- verges to the uniform distribution on the space of perfect matchings for any given graph. We show that it converges in polynomial time (in terms of the variation distance) for all dense enough graphs. Based on this chain we construct a sam- pling scheme that allows us to approximate the permanent of dense 0-1 matrices in polynomial time. Finally we show that the exact computa- tion of the permanent of such matrices is still ~P- complete.