She first appears in Episode 2538 as a part of a tour group from Grouchytown (with Otto and Worby). Oscar shows them around Sesame Street, introducing them to the non-Grouch culture of the area. Velma considers herself brave when she becomes the only Grouch on the tour to sample some of the local food (Gordon's normal turkey salad sandwich).
She appears again in Episode 2648, where Oscar now visits Grouchytown, joined by Bob. The episode establishes Velma as the owner and operator of the Break-It Shop (the Grouch version of the Fix-It Shop), where she's seen damaging a young Grouch's new-looking toaster.