The study of photoexcited strongly correlated materials is attracting growing interest since their rich phase diagram often translates into an equally rich out-of-equilibrium behavior, including non-thermal phases and photoinduced phase transitions. With femtosecond optical pulses, electronic and lattice degrees of freedom can be transiently decoupled, giving the opportunity of stabilizing new states of matter inaccessible by quasi-adiabatic pathways. Here we present a study of the ultrafast non-equilibrium evolution of the prototype Mott-Hubbard material V2O3, which presents a transient non-thermal phase developing immediately after photoexcitation and lasting few picoseconds. For both the insulating and the metallic phase, the formation of the transient configuration is triggered by the excitation of electrons into the bonding a1g orbital, and is then stabilized by a lattice distortion characterized by a marked hardening of the A1g coherent phonon. This configuration is in stark contrast with the thermally accessible ones - the A1g phonon frequency actually softens when heating the material. Our results show the importance of selective electron-lattice interplay for the ultrafast control of material parameters, and are of particular relevance for the optical manipulation of strongly correlated systems, whose electronic and structural properties are often strongly intertwinned.