© 2015 2015 Taylor & Francis. This paper provides a novel perspective in the protein structure prediction (PSP) problem. The PSP problem focuses on determining putative 3D structures of a protein starting from its primary sequence. The proposed approach relies on a multi-agent system (MAS) perspective, where concurrent agents explore the folding of different parts of a protein. The strength of the approach lies in the agents ability to apply different types of knowledge, expressed in the form of declarative constraints, to prune the search space of folding alternatives. The paper makes also an important contribution in demonstrating the suitability of a general-purpose graphical processing unit approach to implement such MAS infrastructure, with significant performance improvements over the sequential implementation and other methods.