The aim of this study is to characterize the optically faint submillijansky (sub-mjy) radio population, exploring its nature and evolution, and thus to complete recent studies which have successfully done this for optically bright sources. In order to achieve this, the VLT/VIMOS was used to obtain spectra of several tens of galaxies that are part of the Phoenix Deep Survey (PDS), a multiwavelength survey based on deep 1.4 Ghz radio imaging, reaching well into the sub-100 μJy level. The analysis of the first set of observations reveal 32 sources with a secure redshift determination having optical magnitudes 19≤R≤24 mag. Of these, 34% are star-forming galaxies, 22% are identified as Seyfert galaxies, showing active galactic nucleus signatures, 6% have absorption lines only, and the remaining 38% show narrow lines that do not allow detailed spectral classification (mainly because they are at high redshifts, or due to spectrum with poor signal-to-noise ratio). On the other hand, the sample considered in this study clearly indicates that optically faint (R≥ 19 mag) sub-mJy radio sources tend to be at higher redshifts, and have fainter radio fluxes, a result which confirms indications from previous work.