First-line triplet chemotherapy including a taxane may prolong survival in patients with metastatic esophagogastric cancer. The added toxicity of the taxane might be minimized by using nab-paclitaxel. The aim of this phase I study was to determine the feasibility of combining nab-paclitaxel with the standard of care in the Netherlands, capecitabine and oxaliplatin (CapOx). Patients with metastatic esophagogastric adenocarcinoma received oxaliplatin 65 mg/m2 on days 1 and 8, and capecitabine 1000 mg/m2 bid on days 1–14 in a 21-day cycle, with nab-paclitaxel on days 1 and 8 at four dose levels (60, 80, 100, and 120 mg/m2, respectively), using a standard 3 + 3 dose escalation phase, followed by a safety expansion cohort. Baseline tissue and serum markers for activated tumor stroma were assessed as biomarkers for response and survival. Twenty-six patients were included. The first two dose-limiting toxicities (i.e., diarrhea and dehydration) occurred at dose level 3. The resulting maximum tolerable dose (MTD) of 80 mg/m2 was used in the expansion cohort, but was reduced to 60 mg/m2 after three out of eight patients experienced diarrhea grade 3. The objective response rate was 54%. The median progression-free (PFS) and overall survival were 8.0 and 12.8 months, respectively. High baseline serum ADAM12 was associated with a significantly shorter PFS (p = 0.011). In conclusion, albeit that the addition of nab-paclitaxel 60 mg/m2 to CapOx may be better tolerated than other taxane triplets, relevant toxicity was observed. There is a rationale for preserving taxanes for later-line treatment. ADAM12 is a potential biomarker to predict survival, and warrants further investigation.