Veracruz sauce is a tomato-based sauce from the region in the Gulf Coast of Mexico that features tomatoes, capers, olives, oregano and bay leaves. If you're thinking that this sauce is reminiscent of a Mediterranean dish, you aren't wrong—these are definitely classic Mediterranean ingredients!