From Muppet Wiki

Natalie is a cow who first appeared as a background character on Sesame Street. She got her name in a Sesame Street News Flash sketch where she was managed by a cat. In another sketch where she was looking for a home, she was also known as Lola.

She also appeared on A Muppet Family Christmas, performed by Richard Hunt.