How old is the expression “老百姓”？ I have searched on line text bases, especially for 三国志 since the 2010 television version of that is what made me wonder. But I do not seem to get reliable results that way. Perhaps if I understood the data bases better I could do better. But certainly my text base searches will not be a good as asking here.

I wail mention, though it is not important evidence, that the 2010 TV series often uses just 百姓 rather than 老百姓.
百姓:
  
  释义：战国之前是对贵族的统称，战国之后，楚对平民的通称。《诗经·雅·天保》“群黎百姓”郑玄笺：“百姓，官族姓也。”
  现今指平民，普通人。也称“老百姓”。
  
  Before the Warring States period, it was a general term for nobles. After the Warring States period, Chu's general name for civilians. Today it refers to civilians, ordinary people. Also known as "The people"


Also: 黎民百姓

百姓 was originally referring to the noble clans united under 黃帝 against the 九黎族 under 蚩尤. After defeating  黎族, 黎民 was taken as slaves by the 百姓. Eventually, 黎民 and 百姓 merged to become 黎民百姓, meaning: "common people"

The relationship between 百姓 and 黎民 was similar to Romans and their slaves