Well, the C-130 has been pretty much everywhere pretty much forever -- not sure if anyone in the military in the last 5 decades or so has not been in and/or near them at some point?
My Mi-26 experience was as a staff tech (military, but as part of a humanitarian effort) airlifting medical trucks into a flood-struck area in India, like, 30 years ago or so, but as I understand it, they're still used pretty widely outside NATO, even today.