Storage device performance prediction is a key element of self-managed storage systems. This work explores the application of a machine learning tool, CART models, to storage device modeling. Our approach predicts a device?s performance as a function of input workloads, requiring no knowledge of the device internals. We propose two uses of CART models: one that predicts per-request response times (and then derives aggregate values) and one that predicts aggregate values directly from workload characteristics. After being trained on the device in question, both provide accurate black-box models across a range of test traces from real environments. Experiments show that these models predict the average and 90th percentile response time with a relative error as low as 19%, when the training workloads are similar to the testing workloads, and interpolate well across different workloads.