Merriam-Webster's Eleventh Collegiate Dictionary (2003) lists the term under safe-deposit box, and reports a first-occurrence date of 1874:
safe-deposit box n (1874) : a box (as in the vault of a bank) for safe storage of valuables — called also safety-deposit box
The Ngram chart for safe deposit box (blue line) versus safety deposit box (red line) across the years 1850–2000 shows a consistent advantage for the former over the years, but both forms are alive and well overall:
I suspect that there may be some unidentified difference in regional preference at play here, too: In Texas, when I was growing up there in the 1960s, the term I remember hearing was safety-deposit box; but if that term is standard there, it must be considerably less common than safe-deposit box in other parts of the English-speaking world.
UPDATE: Identifiable locations of early occurrences of the two terms
Many of the earliest occurrences of safe deposit box and safety deposit box in a Google Books search involve court cases, municipal documents, and other localized reports. To see what geographical patterns (if any) these early occurrences fell into, I ran a search for all Google Books occurrences of safe deposit box between 1850 and 1905 and of safety deposit box between 1850 and 1907. Here's how the geographically identifiable results from the two sets of matches were distributed (with the date range for the occurrences in parentheses):
safe deposit box: New York (1870–1905): 34, Pennsylvania (1893–1904): 11, New Jersey (1899–1903): 3, Washington state (1900–1902): 3, Missouri (1889 & 1901): 2, Connecticut (1903 & 1904): 2, Washington, D.C. (1904 & 1905): 2, Illinois (1898): 1, Ohio (1901): 1, Maryland (1904): 1, California (1904): 1
safety deposit box: Illinois (1888–1906): 10, New York (1896–1907): 9, Michigan (1892–1905): 4, Virginia (1895–1906): 4, Ohio (1892–1907): 4, Massachusetts (1892–1906): 3, Wisconsin (1898–1907): 3, Alabama (1901–1906): 3, Missouri (1898 & 1900): 2, Washington state (1900 twice): 2, Iowa (1895): 1, Minnesota (1896): 1, New Hampshire (1899): 1, Pennsylvania (1903): 1, Nevada (1907): 1, Utah (1907): 1
The results for this very early period are quite skimpy, but they do indicate that virtually all instances of either term through 1905 occurred in the United States. Within the United States, the hotbed of safe deposit box appears to have been in the region from Washington, D.C., to Connecticut—and especially New York—with a sprinkling of outliers in the Midwest (Illinois, Missouri, and Ohio) and on the Pacific Coast (Washington state and California).
The greatest concentrations of safety deposit box between 1850 and 1907 were in Illinois and in New York (where instances of the term were far outnumbered by instances of safe deposit box), but individual occurrences pop up (in tiny numbers) across parts of New England (Massachusetts and New Hampshire), the South (Virginia and Alabama), and the states of the U.S. interior (from Utah to Ohio), especially in the northern Midwest (Wisconsin, Minnesota, Iowa, and Michigan).
The numbers are too small to support any confident generalization, but it is interesting to see how widely dispersed safety deposit box was by 1907, given that the commercial center of the United States (New York) showed a strong preference for safe deposit box.
UPDATE: First occurrence in Google Books search results
The first occurrence of safe deposit box that a Google Books search finds is from the record of court testimony (cross examination of Thomas Morrison) on March 3, 1870 in the case of Jerome Bradley v State of New York, reported in [New York] Court of Appeals (1870):
I could not tell how many securities and Government bonds were in that box (which was normally kept "at the New York Safe Deposit, corner of Broadway and Liberty street"]. We put all our securities into our safe box ; we have a book that we make a record in of them, and this identical bond is one of those numbers. I think that the clerical record in that book was made by myself, but I am not positive. Mr. Hoyt was a former partner of mine, and in settling his interest in the firm we turned over to him quite an amount of five-twenty coupon bonds ; he sold those bonds and bought registered bonds ; he handed the registered bonds to me for the purpose of putting them into our Safe Deposit box. I think before putting those bonds in the Safe Deposit box that I made a record of them myself.
So the first occurrence of Safe Deposit box refers to a box for holding valuable possessions kept at the New York Safe Deposit bank in New York City. It seems very possible that the term safe deposit box used by William H. Butler of Brooklyn, New York, in his patent filing of July 28, 1874, for "certain new and useful Improvements in Safe Deposit Boxes" owes the wording of its name to the boxes already in use at the New York Safe Deposit. Butler's filing refers to "improvements in the construction of the small pigeon-hole boxes used in safe-deposit institutions." It then remarks:
The old method of making safe-deposit boxes was to form a section of pigeon-holes with shelves and partitions, held together by knees or angle-iron ...
It thus appears that safe-deposit box may already have been a standard term in New York by 1874, if not by 1870. At the very least, it is clear that boxes designed to slide into secure pigeon holes in a bank vault existed prior to Butler's 1874 patent.