Negative calorie foods (more properly called negative dietary energy foods or NDEFs) are foods which cost the human body more energy to metabolise than the energy they provide. Foods often claimed to be NDEFs are vegetables such as celery, cress, fennel, leek, kale, and fruit such as apples, strawberries, watermelon, pineapple, and lemons. Much like pennies have cost more than a cent to make in the United states since 2005, minting a penny and consuming a portion of a NDEF both result in a net loss which is undesirable in the context of macroeconomics but especially welcome when one is trying to lose weight.
However, that's where the analogy stops. Unlike pennies, whose minting cost depends on supply and demand and can very well exceed their nominal value, food has a built-in maximum energy cost for it to be metabolised. The maximum specific dynamic action (the energy per gram required to metabolise macronutrients and one of the three components of one's total daily energy expenditure (TDEE), the other two being the basal metabolic rate and the energy cost of physical activity) stands at about 40% for protein. This means that even if you consume pure protein (which has about 4 kcal/g), you will still have a net gain in energy will be 2.4 kcal/g. This isn't looking good for some of the claimed NDEFs above, since they are entirely composed of carbohydrates, whose maximum SDA stands at about 15%. While there have been reports that SDA is not solely dependent on the type of food and can be increased by about 40% under certain conditions, until a way is found for it to exceed 100%, food will always have a positive contribution to one's energy levels.
Does this spell doom for the existence of NDEFs? Not exactly. There is one caveat: there is a fourth often-neglected component to one's TDEE, and that is the energy required for thermoregulation. The human body strives to maintain a roughly constant temperature and in order to do so, it generates heat which, of course, as a form of energy, must come from the energy reserves in the body. So, the logical course of action is to find a way to force the body to expend extra energy on heating itself, and indeed "shivering" is a viable, if a tad extreme, way to quickly shed off weight.
So, how can this principle be applied to eating? Since there seems to be no food that costs more energy to metabolise than it provides, the most reasonable solution would be to find a food that costs more to heat up than it provides. There's an obvious candidate for our cold negative-energy treat, and it's water. It already contributes no energy to the body, and if it is cooler than body temperature when consumed, some energy will be expended to bring it up to body temperature. So, good news all around?
Sadly, no. While cold water does indeed require some energy to be heated up, the amount is minuscule. With a specific heat of 1 cal/g/deg by definition (note that this is calories, not kilocalories, which are often confusingly called calories), drinking a glass (250 g) of almost freezing water corresponds to expending 36 kcal for a body temperature of 36 degrees Celsius. To put this number into perspective, you'd need to drink about a quart of almost freezing water to balance out an Oreo or a gallon to balance out four slices of pizza.
Can we do better? Certainly, but not by much. Ice has a respectable specific enthalpy of fusion, which is the energy per gram required for it to turn into water, energy that comes from the body on top of the energy needed to heat the water to body temperature. Ice needs about 80 cal/g to melt, meaning that eating a glass's worth of ice (not much colder than 0 degrees Celsius) would only make you expend a measly further 20 calories. If you can bring yourself and eat it in ice-chip form (perhaps dipping it in water for extra flavour), each 10 g ice-chip corresponds to about -2.25 kcal.
Disclaimers abound when propagating misconceptions about "negative calorie" foods, warning that negative calorie foods aid weight loss only when consumed in moderation. Of course, if those foods truly were NDEFs, eating more of them would lead to even faster weight loss; claiming otherwise is akin to claiming that spending more than you have can lead to bankruptcy only if done in moderation. Even more misleading and potentially harmful advice is to consume large quantities of such foods, especially sugary fruits such as mangoes and pineapples, which can easily add a slew of extra calories if one is harbouring the belief that they can somehow counterbalance the food they had prior.
So, yes, negative dietary energy exists. Unfortunately for us, it isn't in the form of a sweet, tasty treat, but in the form of a cold, crunchy ice cube. Either try to develop an affinity for ice-based cuisine, or stick to more traditional dieting methods. If all else fails, you can always rest easy knowing that the ice cream you're enjoying contains 10-20 calories fewer than the nutritional information label would have you know.