The dairy industry is actively seeking new applications for various types of whey. One promising direction is the development of nutritious ice cream, using a blend of different whey proteins. However, the production of whey ice cream is hindered by the occurrence of quality issues, primarily stemming from a low content of solids, particularly fat and protein. The development of natural components with distinctive technological attributes, such as the ability to bind excess moisture, enhance foaming properties, and replicate the taste of milk fat, is of significant relevance in food science. In this work, we investigated the influence of plant-based structuring ingredients on the viscoelastic characteristics of whey-based ice creams. Notably, mixes such as 0.4% Vianoks C45 + 0.75% oat β-glucan, 0.4% Vianoks C45 + 0.5% yeast β-glucan, and 0.4% Vianoks C45 + 3% whey protein complex + 10% vegetable purée from table beet have been proven to be effective stabilizing compositions. However, attempts to combine the whey protein complex with other types of vegetable purées like zucchini and broccoli did not yield satisfactory results. It has also been found that β-glucan from the yeast Saccharomyces cerevisiae and κ-carrageenan, a component of the Vianoks C45 stabilization system, forms a robust gel within the system. Analysis of the aqueous phase in whey-based ice creams revealed a consistent correlation between water activity, surface tension, and rheological behavior. Finally, the ice creams that exhibited the best viscoelastic characteristics also had the best sensory attributes.