The prediction of protein secondary structure is a classical problem in bioinformatics, and in the past few years several machine learning techniques have been proposed to attack it. From an abstract pattern recognition viewpoint, the problem can be formulated as a (continuous) consistent labeling problem, whereby one has to assign symbolic labels to a set of objects by taking into account potential constraints between nearby objects. Motivated by this observation, in this paper we propose a new approach to the problem based on (optimally trained) relaxation labeling algorithms, a well-known class of iterative procedures that aim at reducing labeling ambiguities and achieving global consistency through a parallel exploitation of local information. Preliminary experiments performed on standard benchmark data confirm the effectiveness of the approach as compared to standard state-of-the-art machine learning predictors.