We optimize the encapsulation of paclitaxel (PTX) into nanocapsules made of a shell of poly(lactide-co-glycolide)-polyethylene glycol and a core of perfluorooctyl bromide (PFOB) to serve as theranostic agents. Two main challenges were met: keeping the imaging moiety (PFOB) encapsulated while loading the polymer shell with a hydrophobic drug very prone to crystallization. Encapsulation is performed by a modified emulsion-evaporation method leading to 120 nm diameter nanocapsules with a drug loading compatible with tumor treatment. The optimized formulation tested in vitro on CT-26 colon cancer cells yields a similar IC50 as the generic Taxol® formulation. In vivo, 19F-MRI shows that PTX encapsulation does not modify the ability of nanocapsules to accumulate passively in CT-26 tumors in mice by the enhanced permeation and retention (EPR) effect. This accumulation leads to a promising and statistically significant twofold reduction in tumor growth as compared with negative control and generic Taxol® group. Altogether these results advocate for an interesting potential of these paclitaxel-loaded theranostic agents.