The complex flow behavior of polymer-based soft colloidal model systems was investigated using steady and oscillatory shear to prove new concepts for advanced rheological characterization. In the very dilute regime we investigated high molecular weight polybutadiene star polymers to quantify the internal relaxation time arising from the polymeric nature of these ultra-soft colloids. The observed shear-induced brush deformation is interpreted in terms of the internal Zimm time τ(z). The observed dependence of τ(z) on matrix viscosity can be explained by shrinkage of the star polymer due to an increasing incompatibility with increasing matrix molecular weight. The influence of the polymeric nature on the characteristic structural relaxation time in the concentrated regime was investigated using non-linear rheology following Wyss et al (SRFS) (2007 Phys. Rev. Lett. 98 238303). Here we used star-like block copolymer micelles to systematically tune the 'softness' of the colloids by variation of the block ratio. A master curve with proper scaling parameters could be generated independent of the degree of colloidal 'softness'. However, the obtained strain-rate independent structural relaxation time τ(0) was not observed in the linear regime. In addition, a high frequency discrepancy was clearly found in all our experimental data. Both reflect the shortcomings of the SRFS approach.