I've two data sources: a legacy one (web service) along with a database one. Now, after i process request, I made changes to both. Just in case of error, I wish to rollback both.

try
{
  legacy.Begin(); db.Begin();
  legacy.MakeChanges(); db.MakeChanges();
}
except (Exception)
{
  legacy.Rollback(); db.Rollback();
}

The issue is, let's say legacy throws throughout Rollback (i.e. network error)? db.Rollback() will not be performed. And the other way around. The answer I see is:

legacy.Begin(); 
try
{
  db.Begin();
  try
  {
      legacy.MakeChanges(); db.MakeChanges();
  }
  except (Exception)
  {
    db.Rollback();
    throw;
  }
}
except (Exception)
{
  legacy.Rollback(); 
  throw;
}

Could it be acceptable? It is possible to better solution?

You're effectivly moving your personal Two Phase Commit transactions. A totally robust solution requries co-operation from both assets in most cases is better done utilizing a 2PC-capable transaction manager.

The essential problem here is you don't have any defense against the failure of your application (he's playing the role of transaction manager) and therefore no guarantee that you could Rollback that legacy. Think about a failure of the application just in the point it had been going to call legcacy.Rollbock(). At this point you habe no record that you simply were in the center of a "transaction" and thus whenever your application returns you've got no reason to visit and execute that Rollback.

Possible approaches:

1). Use true 2PC, this really is only possible in case your WebSerice has transactional abilities (technically possible but practicly unlikely).

2). Tolerate the chance of some inconsistency. Many systems really do that inadvertantly,

3). Attempt the type of recovery you're going for but accept that it could fail. Add some type of audit trail that enables recognition of uncertain final results and therefore enables manual patch-up later. So you could include some type audit logging that will permit you to identify mismtached activities. This is often seen as an type of very manual 2PC approach.