Dmitri Mendeleev arranged his first periodic table according to the number of protons and valency electrons. How did he, and others of his age, know of these subatomic particles and electron shell capacities? Nowadays, we have technology such as electron microscopes that can help us see (referring to another Physics Stack Exchange post regarding whether we can actually see atoms) these subatomic particles, but how did chemists and scientists in general know?
Of course Mendeleev had no idea about protons or electrons. It is he who discovered the integer which we call atomic number, and which was later found to be the number of protons.
The story of this discovery is approximately this. He was preparing to his chemistry course where he was supposed to give a survey of elements. He had to choose some logical order. For this he made little paper cards on which he wrote the element names and their main properties (like chemical valency). Then he tried to arrange the cards in some logical order.
Finally he found that if the cards are ordered according to the atomic weight, then their chemical properties change roughly periodically. This was called the periodic law. It suggested that the elements are arranged in a table...
There were several exceptions to ordering according to the weight. With the corresponding changes the table looked so nice, that Mendeleev was convinced that he discovered some law. The table also had some gaps. Mendeleev had courage to predict that these gaps correspond to the elements which are not discovered yet. He PREDICTED the existence of new elements and predicted some of their properties.
When these new elements were discovered, this essentially proved that the law was correct.
At the time of discovery this was a purely empirical law. Explanation of this law had to wait for the discovery of quantum mechanics and spin and Pauli Principle.
EDIT. These sources make it more precise: he did not do this in one evening while preparing to a lecture, but worked on a textbook (as a part of his duties as a professor of chemistry). The sources give his personal recollections, unfortunately all only in Russian: