Realistically, the first "business" would be right at the very beginning of the concept of private property and the exchange of goods and services. Hereditary shamans or medicine men could be considered "businessmen", I think some would have travelled and peddled their services. There's also been "agribusiness" ever since the Agricultural Revolution millenia ago.
Economics as we understand it resulted from an extremely long-term process with no real beginning or end.
If you want to know when the first businesses with sale-able ownership came about, I couldn't really say.
