Palladium nanoparticles with excellent uniform size and even distribution were prepared on graphene oxide (Pd NPs/GO) by using a simple and environmentally-friendly ultrasonic method in an ice bath. Ultrasonication time and composition ratios of GO and Pd influenced the morphology of the palladium nanoparticles and their electrocatalytic performance. Transmission electron microscopy (TEM) and electrochemical characterization demonstrated that GO acted as a good supportive substrate for controlling the size and activity of palladium nanoparticles. The optimized nanocomposite exhibited high electrochemical activity for electrocatalytic oxidation of glucose in alkaline medium. The Pd NPs/GO nanocomposite was developed as a non-enzymatic biosensor for the determination of glucose with a linear range of 0.2–10 mM, which is nearly insusceptible to common electroactive interfering species. This simple and effective composite platform could potentially be extended to other metal/graphene nanomaterials, and have broad applications in biosensing, fuel cells, and other fields.