The signing took place during a visit by a Gazprom delegation to the Latin American country, which started Thursday.
"The talks resulted in the signing ... of a trilateral memorandum which foresees the joint assessment of the Acero block and marks another step forward to the creation of a new joint venture to produce hydrocarbons in Bolivia," Gazprom said in a news release.
Bolivia is second in Latin America after Venezuela in terms of natural gas reserves (1.5 trillion cubic meters) and has a high gas-bearing potential.
Gazprom and YPFB signed a memorandum of understanding in February 2007 for prospecting and infrastructure projects as well as the training of staff.
The blocks selected by Gazprom experts - Sunchal, Acero and Carohuaicho - are located in southeastern Bolivia within the gas-bearing Subandino Sur basin. Experts estimate they contain up to 300 billion cubic meters of gas.