Efficient application of veterinary blood transfusion approaches for small companion animals requires readily available supply of the donor material. This can be achieved by developing of effective biobanking technologies allowing long-term storage of donor blood components via cryopreservation. Transfusion of an erythrocyte concentrate allows the successful correction of various hematological pathologies, severe bleeding, and etc. While in the past there were several approaches to cryopreserve red blood cells of dogs, to our knowledge there is virtually no data on cryopreservation of feline erythrocytes. In this paper, we performed a comprehensive parameter optimization for low temperature storage of RBCs of both species. Here, the efficiency of single-component and multicomponent cryoprotective media as well as necessary time of pre-incubation with penetrating and non-penetrating cryoprotectants prior to rapid freezing is analyzed. This study showed that glycerol was not sufficient for cryopreservation of red blood cells of the studied species under the investigated conditions. Application of 10% (v/v) ME2SO allowed for a significant reduction of canine and feline erythrocytes hemolysis after thawing. 17.5% hydroxyethyl starch demonstrated the highest cryoprotective activity for both species. It was found that dog RBCs should be incubated in cryoprotective media for 30 min at 22°C prior to freezing, while for cat RBCs 20 min is sufficient. Combination of CPAs was less effective. Presented data may be considered in further studies in veterinary transfusion and blood banking optimization.