In the recent years, reversible logic has emerged as a promising technology having its applications in low power CMOS, quantum computing, nanotechnology, and optical computing. The classical set of gates such as AND, OR, and EXOR are not reversible. Recently a 4 * 4 reversible gate called “TSG” is proposed. The most significant aspect of the proposed gate is that it can work singly as a reversible full adder, that is reversible full adder can now be implemented with a single gate only. This paper proposes a NXN reversible multiplier using TSG gate. It is based on two concepts. The partial products can be generated in parallel with a delay of d using Fredkin gates and thereafter the addition can be reduced to log 2N steps by using reversible parallel adder designed from TSG gates. Similar multiplier architecture in conventional arithmetic (using conventional logic) has been reported in existing literature, but the proposed one in this paper is totally based on reversible logic and reversible cells as its building block. A 4x4 architecture of the proposed reversible multiplier is also designed. It is demonstrated that the proposed multiplier architecture using the TSG gate is much better and optimized, compared to its existing counterparts in literature; in terms of number of reversible gates and garbage outputs. Thus, this paper provides the initial threshold to building of more complex system which can execute more complicated operations using reversible logic.