The problem of work extraction and storage in quantum and nanoscale thermodynamics is of both fundamental and practical importance. Inspired by the relations between information and work, we propose the concept of informational work storage, in contrast with that of mechanical work storage underlying the idealization of a lifted weight. This novel concept of work storage features an information-theoretic notion of work as the ability to increase the information content of a reference system that is referred to as a work storage system. An experimentally realizable informational work storage system using maximally mixed qubits is studied and applied to the problem of single-shot work extraction in various extraction schemes. We show that for a given system state the maximum extractable work is independent of extraction scheme.