A high protein plain yoghurt formulation was optimised using the Euclidian distance on the Napping® test, measuring the distance among formulations sweetened with stevia and standard samples sweetened with sucrose and sucralose. The optimised formulation was validated through temporal dominance of sensations and acceptance tests. The required amounts of the stevias to provide, at a minimum cost, the same sensory characteristics as the standard samples were 55% of stevia 1 (75% rebaudioside A + stevioside), 5% of stevia 2 (95% rebaudioside A), and 40% of stevia 3 (50% rebaudioside A), which was the best stevia mix found in this study. The stevia mix was an excellent alternative in high protein plain yoghurt, since its sensory profile was very similar to those of sucrose and sucralose. Additionally, there was no significant difference with respect to consumer acceptance.