Self-diffusiophoresis of synthetic Janus (Si/Pt) microspheres in the presence of hydrogen peroxide in complex environments is here investigated. We aim to address the single particle dynamics of these active colloids in different viscoelastic fluids. Experimentally, the Janus colloids were dispersed in a dilute polyvinylpyrrolidone (PVP) solution and in a polyacrylamide (PAM) solution in semi-dilute and semi-dilute entangled regime to analyze their Brownian and active motion. These two systems were chosen to probe different relaxation times from relatively short (∼5 ms) for PVP to large (∼14.5 s) for PAM but always smaller than the rotary Brownian motion time scale. Within this regime, we investigate the coupling between the self-propulsion velocity and the medium rheology. Janus particles are found to get physically confined by polymeric entanglements but surprisingly they are able to escape the physical cage in a time scale much shorter than the relaxation time of the polymer solution. This is particularly relevant for application of self-propelling particles in biomedicine, water and soil remediation where complex environments are naturally present.