Arsenic is a highly toxic metalloid available in the environment mainly as arsenite or arsenate. These compounds’ interference with many molecular mechanisms results in several diseases including cancer. Conversely, arsenic is used in therapeutic approaches, however, they are associated with drug resistance. Although some tolerance and toxicity mechanisms of arsenicals in yeast have been enlightened by previous studies, complete understanding, which is important for development of protection and therapy strategies, has not yet been achieved. Comprehensive genome-wide screening is a promising approach for the elucidation of novel genes involved in arsenic-associated mechanisms. The aim in this study was to screen a yeast genome library to characterize novel genes whose overexpression confers resistance to toxic concentrations of arsenate or arsenite in Saccharomyces cerevisiae. The plasmids from the colonies confirmed to be highly-resistant against arsenicals were sequenced to determine the genomic regions and seven genes were selected to clone into expression vectors. The overexpression of Pho86p and Vba3p provided yeast cells with the highest arsenate and arsenite resistance, respectively. Arsenate is a phosphate analogue and taken up by phosphate transporters. Pho86p is an ER-resident protein regulating ER-exit of the phosphate transporter. Therefore, it is reasonable that overexpression of Pho86p provides arsenate resistance. Vacuolar sequestration is a common route for the removal of toxic compounds from the cytosol and Vba3p is a vacuole-located transporter of basic amino acids with a likely role in arsenite resistance. Consequently, the screen in the current study revealed two genes with promising roles for tolerance mechanisms against arsenicals.