Departments and state finance have been around a long time. Budgets much less so. Medieval governments did not have budgets - they had expenses and revenue and tried to keep the two in line with borrowings and irregular taxes (there were also regular taxes). Probably only England had a high degree of central accounting from around 1000 CE. Others had royal personal revenues, dues from subordinate units, a crown domain, revenues raised by administrative units directly (the director of the mint takes a cut as his pay or similar - very common up to the 18th century), often spread across multiple jurisdictions with different tax structures. So a ruler struggled to get a consolidated picture of revenue and expenses, and most did not bother. It was only from the late many European C18 states started to copy Britain and Prussia and have annual budgets.