Automatically managing the evolutionary histories of both schema and data is an attractive feature for temporal object-oriented database management systems (OODBMS). It can make temporal OODBMSs more suitable for many new applications such as CAD, CAM, GIS, etc. However, this feature complicates the implementation of temporal OODBMSs. In this paper, we examined the problems raised by handling schema evolution and related issues about the storage structure in temporal OODBMSs. Then, we proposed a storage structure for temporal OODBMSs which can handle both schema evolution and data histories simultaneously. We also investigated several possible implementations of the storage structure for temporal data maintenance and compared their performance extensively. This work can be used as a basis for implementation of temporal OODBMSs.