Human gut microbiota is associated with obesity. Gut microbiota–derived extracellular vesicles (EVs), lipid coated nanoparticles secreted by bacteria, have been suggested as a communication mechanism between gut microbiota and the host. This study characterized the effect of Roux-en-Y gastric bypass (RYGB) on gut microbiota and gut microbiota–derived EVs in patients with obesity. Fecal samples were collected from 30 recruited patients at baseline and 6 months after surgery. EVs were isolated from fecal samples, and their origin and protein content were analyzed. The number of unique proteins was increased in gut microbiota–derived EVs after the surgery as compared to baseline. A significant difference in both microbiota composition (p = 0.001; PERMANOVA) and microbiota–derived EVs (p = 0.001; PERMANOVA) was observed in response to surgery. Based on 16S rRNA gene sequencing data, a random forest classifier accurately classified both gut microbiota (AUC = 0.93) and EVs (AUC = 0.80) to baseline and after surgery groups. This study found that gastric bypass surgery altered both the composition and characteristics of gut microbiota and gut microbiota–derived EVs in patients with obesity. Thus, gut microbiota–derived EVs may play a role in obesity and influence the health effects of bariatric surgery beyond the gut.