The Shared Rural Network aims to extend 4G coverage to 95% of the UK, no matter which network customers use, by 2025, three years later than first planned.
The deal involves sharing network equipment but almost collapsed last month in a row between operators.
Taxpayers will pay half the £1bn cost, which will include new masts. EE, O2, Three and Vodafone will pay the rest.
The government says the plan will "make poor and patchy rural phone coverage a thing of the past".
It should guarantee coverage to an extra 280,000 premises, along 16,000km (10,000 miles) of roads - particularly in so-called "not-spots", where there is no service at all.
Sign up to our newsletter to receive all the latest news and updates.