Understanding the way motile micro-organisms such as bacteria explore their environment is central to many ecological, medical and biotechnological questions. Here, I will present some recent advances on the actual spatial exploration processes undertaken by flagellated bacteria such as E.coli, undergoing sequences of runs and tumbles, leading to a random-walk. The extreme sensitivity of the motor rotation switch (CCW/CW) to the presence of a phosphorylated protein (CheYP) in its vicinity, leads to a behavioral variability of run-times, characterized by a log-normal distribution . This mechanism prevails in most Newtonian fluids and has important consequences on the residence times at surfaces  as well as the large scale transport and dispersion in confined environments . However when the surrounding fluid is a yield-stress fluid, the locally high resistance to penetration takes control of the exploration process and the run persistence time distribution is strongly affected by the mechanical bending of the flagella bundle, hence controlling the spatial diffusivity as well as the onset of a motility barrier. References:  N. Figueroa-Morales et al Phys.Rev.X, 10, 021004 (2020).  G.Junot et al., Phys.Rev.Lett., 128, 248101 (2022).  N.Figueroa-Morales et al; Science Advances, 6, eaay0155 (2020).