Measuring with high precision the electrical resistance of highly ordered natural graphite samples from a Brazil mine, we have identified a transition at ~350 K with ~40 K transition width. The step-like change in temperature of the resistance, its magnetic irreversibility and time dependence after a field change, consistent with trapped flux and flux creep, and the partial magnetic flux expulsion obtained by magnetization measurements, suggest the existence of granular superconductivity below 350 K. The zero-field virgin state can only be reached again after zero field cooling the sample from above the transition. Paradoxically, the extraordinarily high transition temperature we found for this and several other graphite samples is the reason why this transition remained undetected so far. The existence of well ordered rhombohedral graphite phase in all measured samples has been proved by x-rays diffraction measurements, suggesting its interfaces with the Bernal phase as a possible origin for the high-temperature superconductivity, as theoretical studies predicted. The localization of the granular superconductivity at these two dimensional interfaces prevents the observation of a zero resistance state or of a full Meissner state.