Background Effective treatments for dogs with advanced stage mast cell tumors (MCT) remain a pressing need. A micellar formulation of paclitaxel (paclitaxel micellar) has shown promise in early‐phase studies. Hypothesis/Objectives The objective was to demonstrate greater activity for paclitaxel (micellar) compared with lomustine. The null hypothesis was μp = μL (ie, proportion of responders for the paclitaxel micellar and lomustine groups, respectively). Animals Two hundred and fifty‐two dogs with advanced stage nonresectable grade 2 or 3 MCT. Methods Prospective multicenter randomized double‐blind positive‐controlled clinical trial. The primary endpoint was confirmed overall response rate (CORR) at 14 weeks. A secondary endpoint, biologic observed response rate (BORR), also was calculated. Safety was assessed by the characterization and grading of adverse events (AE). Results Overall CORR (7% versus 1%; P = .048) and BORR (23% versus 10%; P = .012) were greater for paclitaxel (micellar) compared with lomustine. Paclitaxel (micellar)‐treated dogs were 6.5 times more likely to have a confirmed response and 3.1 times more likely to experience a biologic observed response. The majority of AE with paclitaxel (micellar) were transient and clinically manageable. Twenty‐seven dogs (33%) receiving lomustine were discontinued because of hepatopathy compared with 3 dogs (2%) receiving paclitaxel (micellar) (P < .0001; odds ratio 26.7). Conclusions and Clinical Importance Paclitaxel (micellar)'s activity and safety profile are superior to lomustine. The addition of an active and novel taxane to the veterinary armamentarium could fill a substantial need and, as its mechanism of action and AE profile do not overlap with currently available TKI, its availability could lead to effective combination protocols.