In England at least, jails came first. Gaols, as they're also called, date back to at least the Medieval Era, and probably even further, but I'm not 100% sure so I won't speculate how far back. Basically every town in Medieval England had a gaol, usually in the local castle, to hold suspected criminals until trial. The conditions were... less than great, to say the least. The holding area was often simply a pit, cellar, or wooden cage outside and open to the elements; you could be held for months on end in that damp cellar/pit/cage; and women were just thrown in with the rest of the suspects. No special protection for them. One woman accused of being a thief was jailed for nearly a year before being found innocent.

Going back to the other part of your question, the modern police force only came about in the late 1700s to early 1800s with the Bow Street Runners and Robert Peel's Metropolitan Police, more of which you can read about in this previous thread.

Sources

Mortimer, Ian. The Time Traveller's Guide to Medieval England. New York: Simon & Schuster, 2010.

This previous answer by /u/dr_john_batman: When did police forces start to become their own unique professions, and not simply militias/armies/levies?