Echoing the roaring success of their bulk counterparts, nano-objects built from organolead halide perovskites (OLHP) present bright prospects for surpassing the performances of their conventional organic and inorganic analogues in photodriven technologies. Unraveling the photoinduced charge dynamics is essential for optimizing the optoelectronic functionalities. However, mapping the carrier-lattice interactions remains challenging, owing to their manifestations on multiple length scales and time scales. By correlating ultrafast time-resolved optical and X-ray absorption measurements, this work reveals the photoinduced formation of strong-coupling polarons in CH3NH3PbBr3 nanoparticles. Such polarons originate from the self-trapping of electrons in the Coulombic field caused by the displaced inorganic nuclei and the oriented organic cations. The transient structural change detected at the Pb L3 X-ray absorption edge is well-captured by a distortion with average bond elongation in the [PbBr6]2- motif. General implications for designing novel OLHP nanomaterials targeting the active utilization of these quasi-particles are outlined.