We investigate the shear-induced structure formation of colloidal particles dissolved in non-Newtonian fluids by means of computer simulations. The two investigated visco-elastic fluids are a semi-dilute polymer solution and a worm-like micellar solution. Both shear-thinning fluids contain long flexible chains whose entanglements appear and disappear continually as a result of Brownian motion and the applied shear flow. To reach sufficiently large time and length scales in three-dimensional simulations with up to 96 spherical colloids, we employ the responsive particle dynamics simulation method of modeling each chain as a single soft Brownian particle with slowly evolving inter-particle degrees of freedom accounting for the entanglements. Parameters in the model are chosen such that the simulated rheological properties of the fluids, i.e., the storage and loss moduli and the shear viscosities, are in reasonable agreement with experimental values. Spherical colloids dispersed in both quiescent fluids mix homogeneously. Under shear flow, however, the colloids in the micellar solution align to form strings in the flow direction, whereas the colloids in the polymer solution remain randomly distributed. These observations agree with recent experimental studies of colloids in the bulk of these two liquids.@en