A method was developed for the preparation of rehydratable lyophilized red blood cells (RL RBCs) that hold promise as cell-based oxygen carriers for transfusion medicine. The maintenance of normal cellular deformability is essential for the successful development of cell-based oxygen delivery systems. Improper deformability of RBCs can lead to hemolysis if too fragile or microvascular occlusion if too rigid. We developed an aldehyde stabilization method that is based on the use of paraformaldehyde polymers that complement the function of spectrin as a structural unit with conformational flexibility. Three types of in vitro deformability studies (filter transit, pipette aspiration, and atomic force microscopy) and in vivo intravital microscopy were performed to characterize the deformability of RL RBCs. When considered with safety data from previously reported studies in dogs, the results of these studies indicate that paraformaldehyde-modified RL RBCs have visco-elastic deformability properties that are in the nonpathological range.