The mechanisms by which some melanoma cells adapt to Serine/threonine-protein kinase B-Raf (BRAF) inhibitor therapy are incompletely understood. In the present study, we used mass spectrometry-based phosphoproteomics to determine how BRAF inhibition remodeled the signaling network of melanoma cell lines that were BRAF mutant and PTEN null. Short-term BRAF inhibition was associated with marked changes in fibronectin-based adhesion signaling that were PTEN dependent. These effects were recapitulated through BRAF siRNA knockdown and following treatment with chemotherapeutic drugs. Increased fibronectin expression was also observed in mouse xenograft models as well as specimens from melanoma patients undergoing BRAF inhibitor treatment. Analysis of a melanoma tissue microarray showed loss of PTEN expression to predict for a lower overall survival, with a trend for even lower survival being seen when loss of fibronectin was included in the analysis. Mechanistically, the induction of fibronectin limited the responses of these PTEN-null melanoma cell lines to vemurafenib, with enhanced cytotoxicity observed following the knockdown of either fibronectin or its receptor α5β1 integrin. This in turn abrogated the cytotoxic response to BRAF inhibition via increased AKT signaling, which prevented the induction of cell death by maintaining the expression of the pro-survival protein Mcl-1. The protection conveyed by the induction of FN expression could be overcome through combined treatment with a BRAF and PI3K inhibitor.