The increasing quantity of solid waste due to Date seeds in the Arab world poses environmental concerns about their disposal in landfills. On the other hand, the indiscriminate consumption of the earth resources to obtain solid gravel to produce concrete makes these resources less available. Therefore, it is necessary to find alternative materials to be used in concrete to mitigate this problem. This study aimed at investigate the possibility of producing sustainable structural concrete by replacing Coarse Aggregate (CA) with Date Seeds (DS) at various percentages. The research focused on evaluating the compressive strength (at 28 days) and the flexural behavior of concrete mixes containing DS. Seven experimental concrete mixes were prepared using locally available materials, with DS replacing CA at 2%, 4%, and 6% by volume. Lightweight concrete mix was prepared by eliminating completely the CA and replacing it with DS. The possibility of producing no-fines concrete was also explored by preparing mixes with proportions of DS to cement by volume of 1: 6. A total of 21 cubes were tested for compressive strength and density at 28 days, using a water/cement ratio of 0.40 and 1% superplasticizer. Additionally, three beams (containing 2% by volume of DS replacement) were cast to evaluate the modulus of rupture of concrete. The compressive strength test results show that DS can replace CA up to 6%, with compressive strength gradually decreasing as the replacement percentage increases to 2%, 4%, and 6%, respectively. At 6% replacement, the compressive strength reached 26.6 MPa, compared to 33.5 MPa for the control mix, marking a 20.6% reduction. Similarly, at 2% and 4% replacements, the compressive strength recorded 32.1 MPa (4.2% reduction) and 29.6 MPa (11.64% reduction), respectively. The corresponding densities showed similar trends, with fresh density decreasing from 2329 kg/m³ (control mix) to 2256 kg/m³ (2%), 2183 kg/m³ (4%), and 2197 kg/m³ (6%). It is worth noting that the 2% DS replacement ratio achieved the optimal balance of strength and density. The lightweight concrete mix (100% DS replacement) disintegrated in water due to poor cohesion, while the no-fines concrete mix (100% DS replacement) failed upon demolding. EDS and SEM analyses confirmed that the lack of cohesion was primarily due to the structural properties and high-water absorption of DS. Additionally, the physical properties of Date Seeds (DS), Coarse Aggregate (CA), and Fine Aggregate (FA) were determined; Workability increased with higher replacement ratios, while fresh density decreased, particularly in the lightweight concrete mix with 100% DS replacement. Flexural tests on the prepared beams showed that concrete exhibited good bending performance, with an improved modulus of rupture observed at a 2% DS replacement ratio. The findings highlight that DS can serve as a lightweight aggregate, offering a sustainable alternative to traditional CA, provided that the replacement ratios are carefully-selected.