A system and method for satisfying Quality of Service (QoS) attributes (620) for a stream (405, 410) using a storage device (120) with multi-stream capability is described. The storage device (120) may include memory (510, 515, 520) to store data. A host interface (525) may receive requests (345, 350, 415, 420, 425, 430, 435, 440), some of which may be associated with a stream (405, 410). A host interface layer (545) may schedule the requests (345, 350, 415, 420, 425, 430, 435, 440) in a manner that may satisfy the QoS attribute (620) for the stream (405, 410).