Remotely sensed evapotranspiration (ET_RS) is increasingly used for streamflow estimation. Earlier reports are conflicting as to whether ET_RS is useful in improving streamflow estimation skills. We believe that it is because earlier works used calibrated models and explored only small subspaces of the complex relationship between model skills for streamflow (Q) and ET. To shed some light on this complex relationship, we design a novel randomized, large sample experiment to explore the full ET-Q skill space, using seven catchments in Vietnam and four global ET_RS products. For each catchment and each ET_RS product, we employ 10,000 SWAT (Soil and Water Assessment Tool) model runs whose parameters are randomly generated via Latin Hypercube sampling. We then assess the full joint distribution of streamflow and ET skills using all model simulations. Results show that the relationship between ET and streamflow skills varies with regions, ET_RS products, and the selected performance indices. This relationship even changes with different ranges of ET skills. Parameter sensitivity analysis indicates that the most sensitive parameters could have opposite contributions to ET and streamflow skills. Conditional probability assessment reveals that with certain ET_RS products, the probabilities of having good streamflow skills are high and increase with better ET skills, but for other ET_RS products, good model skills for streamflow are only achievable with certain intermediate ranges of ET skills, not the best ones. Overall, our study provides a useful approach for evaluating the value of ET_RS for streamflow estimation.