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(1-9). In such systems the quantum nature of a macroscopic degree of freedom can be revealed and manipulated(10). This opens up appealing perspectives for quantum information technologies(11), 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(12): 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(13,14) and a large exciton-phonon coupling strength g(0). By means of optical and mechanical spectroscopy, we find that g(0)/2 pi is nearly as large as the mechanical frequency, a criterion that defines the ultrastrong coupling regime(15).