Climatic variability influences the hydrological cycle that subsequently affects the discharge in the stream. The variability in the climate can be represented by the ocean-atmospheric oscillations which provide the forecast opportunity for the streamflow. Prediction of future water availability accurately and reliably is a key step for successful water resource management in the arid regions. Four popular ocean-atmospheric indices were used in this study for annual streamflow volume prediction. They were Pacific Decadal Oscillation (PDO), El-Nino Southern Oscillation (ENSO), Atlantic Multidecadal Oscillation (AMO), and North Atlantic Oscillation (NAO). Multivariate Relevance Vector Machine (MVRVM), a data driven model based on Bayesian learning approach was used as a prediction model. The model was applied to four unimpaired stream gages in Utah that spatially covers the state from north to south. Different models were developed based on the combinations of oscillation indices in the input. A total of 60 years (1950-2009) of data were used for the analysis. The model was trained on 50 years of data (1950-1999) and tested on 10 years of data (2000-2009). The best combination of oscillation indices and the lead-time were identified for each gage which was used to develop the prediction model. The predicted flow had reasonable agreement with the actual annual flow volume. The sensitivity analysis shows that the PDO and ENSO have relatively stronger effect compared to other oscillation indices in Utah. The prediction results from the MVRVM were compared with the Support Vector Machine (SVM) and the Artificial Neural Network (ANN) where MVRVM performed relatively better.