Solid–liquid separation is a key unit operation in the wastewater treatment, generally consisting of coagulation and flocculation steps to promote aggregation and increase the particle size, followed by sedimentation, where the particles settle due to the effect of gravity. The sedimentation efficiency is related to the hydrodynamic behavior of the suspended particles that, in turn, depends on the aggregate morphology. In addition, the non-Newtonian rheology of sludges strongly affects the drag coefficient of the suspended particles, leading to deviations from the known settling behavior in Newtonian fluids. In this work, we use direct numerical simulations to study the hydrodynamic drag of fractal-shaped particles suspended in a shear-thinning fluid modeled by the power-law constitutive equation. The fluid dynamics governing equations are solved for an applied force with different orientations uniformly distributed over the unit sphere. The resulting particle velocities are interpolated to compute the aggregate dynamics and the drag correction coefficient. A remarkable effect of the detailed microstructure of the aggregate on the sedimentation process is observed. The orientational dynamics shows a rich behavior characterized by steady-state, bistable, and periodic regimes. In qualitative agreement with spherical particles, shear-thinning increases the drag correction coefficient. Elongated aggregates sediment more slowly than sphere-like particles, with a lower terminal velocity as the aspect ratio increases.