In this paper, we introduce new classes of proximal multi-valued contractions in a metric space and proximal multi-valued nonexpansive mappings in a Banach space and show the existence of best proximity points for both classes. Further, for proximal multi-valued nonexpansive mappings, we prove a best proximity point theorem on starshape sets. As a consequence, we also obtain some new fixed point theorems. Finally, we give some examples to illustrate our main results.