The effect of using a viscoelastic suspending medium on the in-plane hydrodynamic interaction between two equally sized spheres in shear flow is studied experimentally to understand flow-induced assembly behavior (i.e., string formation). A counterrotating device equipped with a Couette geometry is used together with quantitative videomicroscopy. To evaluate the effects of differences in rheological properties of the suspending media, fluids have been selected that highlight specific constitutive features. These include a reference Newtonian fluid (N), a constant-viscosity, high-elasticity Boger fluid (BF), a wormlike micellar surfactant solution with a single dominant relaxation time (WMS), and a broad spectrum shear-thinning elastic polymer solution (ST). As expected, the trajectories are symmetric in the Newtonian fluid. In the BF, the midpoints of the spheres are observed to remain in the same plane before and after the interaction, as in the Newtonian fluid, although the path lines are in this case no longer symmetric. Interactions in the ST and WMS are highly asymmetric. Two fundamentally different kinds of path lines are observed in the WMS and ST: reversing and open trajectories. The type of trajectory depends on the initial configuration of the spheres with respect to each other and on the shear rate. On the basis of the obtained results, shear-thinning of the viscosity seems to be the key rheological parameter that determines the overall nature of the interactions, rather than the relative magnitude of the normal stress differences.