This study focuses on the development of a lightweight, high-performance cementitious composite material reinforced with Poly(vinyl alcohol) (PVA) fiber. The material which contains Poly(vinyl butyral) (PVB) as the sole aggregate has a low average density of 1548 kg/m3 and a compressive strength of about 40 MPa. The flexural strength, impact resistance, and fracture toughness are also evaluated and are found to be improved in comparison to those of lightweight concrete. The addition of PVA fiber further improves ductility, fracture toughness and impact resistance. The increase in fracture toughness was found to be linear with increasing fiber volume fraction. Comparisons are made with a lightweight concrete of equal density, and a normal-weight concrete. A model based on fiber bridging mechanics and the rule of mixtures is developed to characterize the fracture toughness, and a good correlation is obtained for the materials tested when experimental results are compared to those predicted by the model.