We have first succeefully synthesized the sodium cobalt oxyhydrate superconductors using KMnO4 as a de-intercalating and oxidizing agent. It is a novel route to form the superconductive phase of NaxCoO2.yH2O without resorting to the commonly used Br2/CH3CN solution. The role of the KMnO4 is to de-intercalate the Na+ from the parent compound Na0.7CoO2 and oxidize the Co ion as a result. The higher molar ratio of KMnO4 relative to the sodium content tends to remove more Na+ from the parent compound and results in a slight expansion of the c-axis in the unit cell. The superconducting transition temperature is 4.6-3.8 K for samples treated by the aqueous KMnO4 solution with the molar ratio of KMnO4 relative to the sodium content in the range of 0.3 and 2.29.