In this paper, a newly developed 3-dimentional discrete element model (DEM) for gravel-rubber mixtures (GRMs), namely DEM4GRM, that is capable of accurately describing the macro-scale shear response (from small to large deformation) of GRMs in a direct shear box apparatus is presented. Rigid gravel grains are modelled as simple multi-shape clumps, while soft rubber particles are modeled by using deformable 35-ball body-centered-cubic clusters. Mixtures are prepared with different volumetric rubber content (VRC) at 0, 10, 25, 40 and 100%, statically compressed under 30, 60 and 100 kPa vertical stress and then sheared, by closely simulating a reference laboratory test procedure. The variation of micro-scale factors such as fabric, normal and tangential force anisotropy is carefully examined throughout the shearing process and described by means of novel micro-mechanical relationships valid for GRMs. Moreover, strong-force chains are scrutinized to identify the transition from rigid to soft granular skeleton and gain insights on the load transfer and deformation mechanisms of GRMs. It is shown that the development of the fabric and force anisotropy during shearing is closely related to the macro-scale shear strength of GRMs, and strongly depends on the VRC. Besides, strong-force chains appear to be primarily formed by gravel-gravel contacts (resulting in a rigid-like mechanical behavior) up to VRC = 30%, and by rubber-rubber contacts (causing a soft-like mechanical response) beyond VRC = 60%. Alternatively, at 30% < VRC < 60%, gravel-rubber contacts are predominant in the strong-force network and an intermediate mechanical behavior is observed. This is consistent with the behavioral trends observed in the macro- and micro-mechanical responses.