Whether you call it an aioli or a sauce, the origins of aioli's date back as far as the Roman Empire. They are traditionally made with garlic, egg yolk, oil, and lemon juice, and are similar to mayonnaise. Aioli has a very thick texture and a rich flavor. It is often used in Mediterranean, Italian, French, and Spanish cuisine.