We show that it is possible to use high rate co-evaporation of Al and Si onto room temperature substrates to achieve a novel two-phase nanoscale microstructure. These nanocomposites have a hardness as high as 4GPa (Al-23at.%Si), and display noticeable plasticity. Films with compositions of Al-12at.%Si and pure Al (used as baseline) were analyzed using transmission electron microscopy (TEM). The scale of the Al-12at.%Si microstructure is an order of magnitude finer compared to that of pure Al films. It consists of a dense distribution of spherical nanoscale Si particles separating irregularly-shaped small Al grains. These new structures may have a mechanical performance advantage over conventional single phase nanomaterials due to the role of the dispersed hard phase in promoting strain hardening.