Background: Neither paclitaxel plus trastuzumab (P-H) nor docetaxel-cyclophosphamide plus trastuzumab (TC-H) have been prospectively compared in HER2-positive early-stage breast cancer (EBC). A randomized trial was performed to assess the feasibility of a larger study. Methods: Lower-risk HER2-positive EBC patients were randomized to either P-H or TC-H treatment arms. The co-primary feasibility outcomes were: ≥75% patient acceptability rate, active trial participation of ≥50% of medical oncologists, ≥75% and ≥90% treatment completion, and receipt rate of planned cycles of chemotherapy, respectively. Secondary outcomes: Febrile neutropenia (FN) rate, treatment-related hospitalizations, health-related quality of life (HR-QoL) questionnaires. Analyses were performed by per protocol and intention-to-treat. Results: Between May 2019 and March 2021, 49 of 52 patients agreed to study participation (94% acceptability rate). Fifteen (65%) of 23 medical oncologists approached patients. Rates of FN were higher (8.3% vs. 0%) in the TC-H vs. P-H arm. Median (IQR) changes in scores from baseline in FACT-Taxane Trial Outcome Index at 24 weeks were −4 (−10, −1) vs. −6.5 (−15, −2) for TC-H and P-H arms, respectively. Conclusions: A randomized trial comparing P-H and TC-H was feasible. Expansion to a larger trial would be feasible to explore patient-reported outcomes of these adjuvant HER2 chemotherapy regimens.