The public library along with a small bookstore were officially inaugurated on 23 May 1876 by the Governor of Taganrog Admiral Johan Hampus Furuhjelm.

In March 1878 the Public Library moved into another building granted by the City Council on Petrovskaya Street.

Among the first subscribers were the writer Anton Chekhov, historian Pavel Filevsky, Vladimir Bogoraz, artists Seraphima Blonskaya and Dmitri Sinodi-Popov.

In 1904, following Chekhov's death, the library was named after the playwright and short-story writer.

The music department of the library is located at the historical Tchaikovsky House in Taganrog.