Composite hydrogels based on pullulan (HP) and poly(vinyl alcohol) (PVA) were both prepared by simple chemical crosslinking with sodium trimethaphosphate (STMP) or by dual crosslinking (simultaneously chemical crosslinking with STMP and physical crosslinking by freeze-thaw technique). The resulting hydrogels and cryogels were designed for tissue engineering applications. PVA, with two different molecular weights (47,000 and 125,000 g/mol; PVA47 and PVA125, respectively), as well as different P/PVA weight ratios were tested. The physico-chemical characterization of the hydrogels was performed by FTIR spectroscopy and scanning electron microscopy (SEM). The swelling kinetics, dissolution behavior, and degradation profiles in simulated physiological conditions (phosphate buffer at pH 7.4) were investigated. Pullulan concentration and the crosslinking method had significant effects on the pore size, swelling ratio, and degradation profiles. Cryogels exhibit lower swelling capacities than the conventional hydrogels but have better stability against hydrolitic degradation. Biocompatibility of the hydrogels was also investigated by both MTT (3-(4,5-dimethylthiazol-2-yl)-2,5-diphenyltetrazolium bromide) and LDH (lactaten dehydrogenase) assay. The MTT and LDH assays proved that dual crosslinked HP/PVA125 (75:25, w/w) scaffolds are more biocompatible and promote to a greater extent the adhesion and proliferation of L929 murine fibroblast cells than chemically crosslinked HP/PVA47 (50/50, w/w) scaffolds. Moreover, the HP/PVA125 cryogel had the best ability for the adipogenic differentiation of cells. The overall results demonstrated that the HP/PVA composite hydrogels or cryogels are suitable biomaterials for tissue engineering applications.