Where are you running the query from? If it is from .Net code, there is a query timeout (and a connection timeout) that can cause this. The default value is 15 seconds if I am not mistaken. To see if that is the problem, you can try to run the same query from SSMS. Even so, if it takes 15 seconds or more, investigate why it is taking so long. It could be that the number of rows affected is very large (in which case, you could delete in smaller chunks), or may be that the rows/table is locked by some other process.