A multi-stage secret sharing (MSS) scheme is a method of sharing a number of secrets among a set of participants, such that any authorized subset of participants could recover one secret in every stage. The first MSS scheme was proposed by He and Dawson in 1994, based on Shamir’s well-known secret sharing scheme and one-way functions. Several other schemes based on different methods have been proposed since then. In this paper, the authors propose an MSS scheme using All-Or-Nothing Transform (AONT) approach. An AONT is an invertible map with the property that having “almost all” bits of its output, one could not obtain any information about the input. This characteristic is employed in the proposed MSS scheme in order to reduce the total size of secret shadows, assigned to each participant. The resulted MSS scheme is computationally secure. Furthermore, it does not impose any constraint on the order of secret reconstructions. A comparison between the proposed MSS scheme and that of He and Dawson indicates that the new scheme provides more security features, while preserving the order of public values and the computational complexity.