Absolutely! Boiled potatoes can also be a delicious option to go with pork tenderloin. Just make sure to season them well and add some herbs for extra flavor.