What can I substitute for Mayonnaise in a traditional potato salad? I wanted to make a Potato Salad that was going to be exposed to fairly extreme heat during an upcoming picnic and wanted to make sure it wouldn't spoil as quickly as it does sometimes.  Is there something other than Mayo that I can use to bind it together - here is the rest of the recipe:


5 cups peeled and cubed potatoes
1/3 cup lemon juice
1/4 cup vegetable oil
2 teaspoons white sugar
1 1/2 teaspoons seasoning salt
1 1/2 teaspoons Worcestershire sauce
1 teaspoon ground mustard
1/4 teaspoon ground black pepper
1/4 cup chopped green onions
1/3 cup chopped celery
3 tablespoons chopped fresh parsley
Direct substitution options would include sour cream, plain yogurt, or cottage cheese pureed in your blender to do a one-to-one substitution, but I don't know that these would necessarily solve your issue of having the salad sit out with ingredients that could spoil.  

This question has a whole list of substitutes.  Tofu is one that might suit your needs, although it would change the flavor profile.

Consider instead a German potato salad, which does not have mayonnaise to begin with.  Yes, this departs from your original recipe, but it will definitely solve your issue.