A storage device includes a data storage media and a control unit. The control unit is electrically coupled to the data storage media and configured for controlling the data storage media. The control unit is configured to receive a task assignment packet from a host. The task assignment packet includes a plurality of tasks and each of the tasks has a task ID. The control unit is configured to sort the tasks and generate an execution order for the tasks and reply the host with a task arrangement packet according to the execution order. A task execution method of the storage device and the host and a task execution method thereof are also provided.