Six natural polymers were tested as binders in a novel concrete composite for construction purposes. Cubic composite samples were made from the different binders and sand, and the compression strengths were evaluated. Concentration sweeps found the highest strength for each natural polymer composite. The composites’ mechanical performance was then compared with the polymers’ cohesive and adhesive strengths and discussed, based on their molecular properties. The adhesion was found to be essential to the composite's compression strength. Gelatin and chitosan showed good adhesive properties. Gelatin-based composites presented the highest mean compression strength of 59.6 MPa, chitosan 8.8 MPa. The lowest mean compression strength was found for κ-carrageenan-based composites with 1.6 MPa. Gelatin-based composites were found to be most suitable for construction applications.