This paper studies how streamflow predictability varies with basin characteristics. We introduce an index of basin complexity that is based on a model of least statistical complexity that is needed to reliably predict daily streamflow of the basin. We then relate it with climate, vegetation and soil characteristics of the basin. Daily streamflow is modeled using k nearest neighbor model of lagged streamflow that predicts next time step streamflow based on the occurrences of similar streamflow events from the past. In order to calculate basin complexity, we identify difficult streamflow events of the basin and then use Vapnik-Chervonenkis generalization theory, which trades off model performance with Vapnik-Chervonenkis dimension (i.e., a measure of model complexity), to find a k nearest neighbor model of appropriate complexity for predicting a difficult streamflow event of the basin. The average of selected model complexities corresponding to difficult events is then defined as the basin's complexity. Basin complexity of 412 Model Parameter Estimation Experiment basins from continental United States are then related with its six basin characteristics. All the characteristics have been derived from the Model Parameter Estimation Experiment database to represent climate, vegetation and soil characteristics of the basins in a concise manner. Results find that more complex basins that are drier have less seasonal rainfall, vegetation with more storage capacity (i.e., smaller 5-week Normalized Difference Vegetation Index gradient), and faster responsive soils. The results reaffirm prior observations that minimum complexity that is required to model a basin depends on its climate and landscape characteristics (e.g., complex models do not perform well in dry basins).