They instructed their transport ministers to decide details on the funding and launching of Galileo at their meeting later this month. They also gave the go-ahead for setting up a joint venture with the European Space Agency.
The European Commission, the EU's executive body, welcomed the agreement.
"It's very important that the union's heads of government have decided to support Galileo," a European Commission official said.
So far, €180m (£111m) has been spent on the project, which rivals the GPS built by the US military and used in many civilian applications for locating or timekeeping.
The EU is now looking for its 15 member states to pay a further €450m (£279m). Together with €550m (£340m) pledged by the European Space Agency, this will assure funding for Galileo's 2001-2006 development phase, said the Commission official.
Germany, the Netherlands and the UK have until now avoided a final decision to back the costly Galileo project. The commission official, who requested anonymity, said the recent cooling in the US/EU relationship played an important part in winning over these doubters.
"Recent incidents including the steel dispute have made all member governments of the EU think twice about relying on the US GPS," he said.
The decision two weeks ago by the US to impose import tariffs of up to 30% on foreign steel has provoked a groundswell of condemnation in the EU.
Comments earlier this month by the US Department of State saying it saw no compelling need for Galileo because GPS would meet the world's needs for the foreseeable future, "nudged the more reluctant heads of state along in agreeing to back the project", the official said.
The State Department said that if the EU did decide to build Galileo, the US wanted co-operation to ensure that the European system could operate in coordination with GPS.
The Pentagon raised objections about the plan last December, warning that future enemies might make use of the proposed civilian European system in a war with the West.