Polyelectrolyte complexes of sodium alginate and gelatin obtained from cold-blooded fish were studied for potential application as structure-forming agents in food hydrogels. The mass ratio of sodium alginate to gelatin plays a decisive role in the sol-gel transition and rheological behavior of the complexes. Differences in the sol-gel transition temperature were observed upon heating and cooling, as is typical for such materials. We investigated the characteristics of this transition by measuring the isothermal changes in the elastic modulus over time at a constant frequency and the transition temperature at a range of frequencies. The kinetic nature of this transition depends on the composition of the complexes. A characteristic alginate-gelatin mass ratio is the ratio at which maximum transition temperature as well as elastic modulus and viscosity (rheological parameters) values are obtained; the characteristic mass ratio for these complexes was found to be 0.06. Calculation of the ionic group ratios in the biopolymers that form complexes and comparison of these data with the turbidimetric titration results clarified the origin of these maxima. Measuring the viscoelastic properties and the creep-elastic recoil of the samples allowed us to characterize these materials as viscoelastic media with a viscosity in the order of 103-104 Pa·s and an elastic modulus in the order of 102-103 Pa. These values drastically decrease at a certain stress threshold, which can be treated as the gel strength limit. Therefore, the observed rheological behavior of gels formed by fish gelatin modified with sodium alginate characterizes them as typical viscoelastic soft matter.