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-agents approach, 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 local space of folding alternatives. The paper demonstrates the suitability of a GPU approach to implement such multi-agent infrastructure, with significant improvements in speed and quality of solutions w.r.t. other methods (e.g., based on fragments assembly approaches). © 2013 IEEE.