Methods and apparatus for host-side Serial ATA Native Command Queuing (NCQ) tag management are disclosed. In one aspect, an exemplary apparatus may include a memory and an NCQ tag selection circuit in communication with the memory. The memory may store information for each of a plurality of different NCQ tag values. The information for each NCQ tag value may indicate whether or not a command having the NCQ tag value has been issued. The NCQ tag selection circuit may examine the information in the memory, and may select an NCQ tag value having information that indicates that a command having the NCQ tag value has not been issued. Systems and architectures including such apparatus are also disclosed.