Polymeric micelles (PM) based on poly(ethylene glycol)-b-poly(N-2-benzoyloxypropyl methacrylamide) (mPEG-b-p(HPMA-Bz)) loaded with paclitaxel (PTX-PM) have shown promising results in overcoming the suboptimal efficacy/toxicity profile of paclitaxel. To get insight into the stability of PTX-PM formulations upon storage and to optimize their in vivo tumor-targeted drug delivery properties, we set out to identify a lead PTX-PM formulation with the optimal polymer composition. To this end, PM based on four different mPEG5k-b-p(HPMA-Bz) block copolymers with varying molecular weight of the hydrophobic block (17–3 kDa) were loaded with different amounts of PTX. The hydrodynamic diameter was 52 ± 1 nm for PM prepared using polymers with longer hydrophobic blocks (mPEG5k-b-p(HPMA-Bz)17k and mPEG5k-b-p(HPMA-Bz)10k) and 39 ± 1 nm for PM composed of polymers with shorter hydrophobic blocks (mPEG5k-b-p(HPMA-Bz)5k and mPEG5k-b-p(HPMA-Bz)3k). The best storage stability and the slowest PTX release was observed for PM with larger hydrophobic blocks. On the other hand, smaller sized PM of shorter mPEG5k-b-p(HPMA-Bz)5k showed a better tumor penetration in 3D spheroids. Considering better drug retention capacity of the mPEG5k-b-p(HPMA-Bz)17k and smaller size of the mPEG5k-b-p(HPMA-Bz)5k as two desirable design features, we argue that PM based on these two polymers are the lead candidates for further in vivo studies.