Lateral diffusion of nano-objects on lipid membranes is a crucial process in cell biology. Recent studies indicate that nanoparticle lateral diffusion is affected by the presence of membrane proteins and deviates from Brownian motion. Gold nanoparticles (Au NPs) stabilized by short thiol ligands were dispersed near a free-standing bilayer formed in a 3D microfluidic chip. Using dark-field microscopy, the position of single NPs at the bilayer surface was tracked over time. Numerical analysis of the NP trajectories shows that NP diffusion on the bilayer surface corresponds to Brownian motion. The addition of bovine serum albumin (BSA) protein to the solution led to the formation of a protein corona on the NP surface. We found that protein-coated NPs show anomalous superdiffusion and that the distribution of their relative displacement obeys Lévy flight statistics. This superdiffusive motion is attributed to a drastic reduction in adhesive energies between the NPs and the bilayer in the presence of the protein corona. This hypothesis was confirmed by numerical simulations mimicking the random walk of a single particle near a weakly adhesive surface. These results may be generalized to other classes of nano-objects that experience adsorption-desorption behaviour with a weakly adhesive surface.