Why is my non clustered index causing this deadlock?

I have an application that runs the following query in multiple parallel threads: update Table1 SET Col1 = 'Some value' WHERE Order_ID = @orderID Order_ID is NOT the primary key on this table, but the @orderID is different for each thread, this update used to run fine until a non-clustered index was introduced: CREATE NONCLUSTERED INDEX MyIndex ON dbo.Table1 (Col2, Col3, Col4 ... Order_ID) INCLUDES (Col5, Col6, Col7 ... Col1) After this index was introduced, the following deadlock started occurring: I considered the deadlock sequence presented on this answer , but I think if that were the case my deadlock should also happen without the index. How could my index be causing this deadlock and how should it be fixed without complete removal of the index? **-- Edit --** This is the .xdl file saved by the SQL Profiler: unknown unknown UPDATE Securities_Fund_Deals SET Market_Deal_Reference = '[No Deal Ref]' WHERE Securities_Orders_ID = 100002 unknown unknown UPDATE Securities_Fund_Deals SET Market_Deal_Reference = '[No Deal Ref]' WHERE Securities_Orders_ID = 100003