The best place to store your red potatoes is in a pantry, cellar, or somewhere cool and dark. Do not store them in the refrigerator as the cold can make them hard and mushy. Avoid keeping them with onions and garlic as they can speed up the spoilage process.