1839, "cafe," American English, from Mexican Spanish cafeteria "coffee store," from café "coffee" (see coffee) + Spanish -tería "place where something is done" (usually business). Sense shifted by 1890s to "self-service dining establishment." The ending came to be understood popularly as meaning "help-yourself" and was extended to new formation with that sense from c. 1923.
Examples of the thing itself date to 1885, but they seem to have become established first in Chicago in the early 1890s by social and philanthropic organizations (such as the YWCA) to offer working girls affordable, fast, light meals in a congenial atmosphere. Their popularity waned after c. 1926, eclipsed by coffee shops, lunch counters, and sandwich shops. Industrial plants began to add them in 1915; schools and colleges followed.