The exploitation of coal and the disposal of waste plastic present significant environmental and economic challenges that require sustainable and profitable solutions. In response, we propose a renewable construction composite material of coal-based thermoplastic composite (CTC) that can be made from low-grade coal and plastic waste. We developed and tested the hot-press fabrication method for this CTC, using coal with a maximum particle size of 4.75 mm and recycled high-density polyethylene (HDPE). The effects of the coal fraction (50–80 wt.%) on compressive properties, thermal properties, microstructure, and ecological and economic efficiencies of the CTC were investigated. Test results revealed that the compressive strength and modulus decrease as the coal fraction increases. However, the thermal properties, including thermal conductivity and specific heat, increase with higher coal contents. Compared to concrete, the CTC has about half the thermal conductivity and twice the specific heat, making it a more energy-efficient construction material. Microstructure testing helped to reveal the mechanisms behind the above behaviors of CTC from the observation of binder volume, bonding quality between coal and HDPE, and porosity variation. The life cycle analysis indicated that the CTC production reduced embodied energy, carbon footprint, and cost by up to 84%, 73%, and 14%, respectively. Therefore, we recommend the CTC with 50–70% coal fraction as an innovative construction material with satisfied mechanical and thermal properties, better cost efficiency, and a reduced ecological impact.