The present research investigated bio-based construction material based on hemp shives and gypsum. Low-density material was developed with densities of 200, 300, and 400 kg/m3. Simple yet robust production technology was used. For the first time a binder for bio-composites obtained from phosphogypsum was used and properties were compared to commercial gypsum. CO2 negative building material was developed with up to 92 kg CO2 ekv./m3 entrapped. Both physical and mechanical properties were studied. Thermal conductivity was in the range from 0.058 to 0.101 W/(m·K) and compressive strength from 0.10 to 0.57 MPa. Biodeterioration test results showed that the pH of 5.60–6.55 for bio-composites promoted a rapid mold growth. Mold growth was slightly lower for composites with higher gypsum content, while phosphogypsum induced more rapid mold growth. Cladosporium, Rhizopus, Chaetomium and other molds were observed on samples even at an early stage of testing giving a serious concern about only limited application in dry conditions for such gypsum-based bio-composite.