The effects of temperature fluctuation ranges, number of fluctuations carried out, and packaging during frozen storage on the texture of potato tissue in terms of compression, shear, and tension rheological parameters were assessed through data generated according to a factorial design using principal component analysis (PCA). Five ranges of fluctuation (–24 °C to –18 °C, –18 °C to –12 °C, –12 °C to –6 °C, –24 °C to –12 °C and –18 °C to –6 °C) applied 2, 4, 8, 16, 24, and up to 32 times on unpacked and pre-packed frozen potatoes, were considered. The controls were unpacked and prepacked frozen tissues thawed immediately without undergoing any fluctuation. In addition, several geometrical, technological, and chemical parameters were determined. PCA showed that maximum shear force, Fs was the best rheological parameter for differentiation of the structural damage and softening occurring in the tissue at each treatment, which was closely related to its duration, TTd. PCA did not permit complete discrimination between the five fluctuation ranges, but it clearly separated samples subjected to –18 °C/–6 °C from those subjected to –24 °C/–18 °C. Frozen samples undergoing up to four fluctuations formed a separate cluster from those undergoing a higher number. Analysis also clearly separated unpacked from pre-packed samples in response to slower freezing rates reached in the latter.