No, avoid eating Corn Tortilla when you are on a paleo diet, as it is a grain and it is forbidden to consume cereals in the paleo diet .