An index just on that column will probably not be useful. What you'll likely need to do is create indexes for the various queries and ensure that the IsDeleted is part of each index.

If you can post a couple of example queries I can probably help you further.