Edible films based on pullulan/gelatin (PUL/GEL) blends (100/0, 75/25, 50/50, 25/75, and 0/100) incorporated with various concentrations (0, 0.5, 1, 2%) of potassium sorbate (KS) were prepared and characterized. The results showed that the mixing of PUL and GEL solutions led to a phase separation. At ratio PUL:GEL = 50:50 the polymers segregated into the biggest microscopic domains. The incorporation of KS resulted in an increase in the size of microparticles. The crystallinity and tensile strength increased as the GEL content in the films increased. As proven by findings of wide-angle X-ray diffraction, the amorphous nature of PUL-rich films was converted to semi-crystalline-like, possibly as a result of reflection of the recrystallized KS. On the other hand, the KS decreased the crystalline character of the GEL-rich films. The incorporation of KS reduced the glass transition temperature, suggesting that the preservative acted as plasticizer for the films. Consequently, the KS reduced mechanical strength and stiffness and improved stretchability of the films. Additionally, the KS increased the pH, UVB-barrier capacity, and moisture absorption properties (at water activities >0.52). After the KS addition, the GEL-containing films showed a much more intensive yellowing compared to the pure PUL films. Furthermore, the increase in GEL concentration favored the recrystallization of KS.