Recent progress in nanotechnology has allowed the fabrication of new hybrid systems in which a single two-level system is coupled to a mechanical nanoresonator. In such systems the quantum nature of a macroscopic degree of freedom can be revealed and manipulated. This opens up appealing perspectives for quantum information technologies, and for the exploration of the quantum-classical boundary. Here we present the experimental realization of a monolithic solid-state hybrid system governed by material strain: a quantum dot is embedded within a nanowire that features discrete mechanical resonances corresponding to flexural vibration modes. Mechanical vibrations result in a time-varying strain field that modulates the quantum dot transition energy. This approach simultaneously offers a large light-extraction efficiency and a large exciton-phonon coupling strength g0. By means of optical and mechanical spectroscopy, we find that g0/2 π is nearly as large as the mechanical frequency, a criterion that defines the ultrastrong coupling regime.