The Myanmar government started gauging telecommunications companies’ interest in nationwide licenses on Tuesday ahead of its plans to issue two permits by June.The move is part of the government’s plan to open its underdeveloped and potentially lucrative telecommunications market to large-scale foreign investment. It comes amid a flurry of other changes aimed at bolstering the country’s impoverished economy.

While several companies have expressed interest, challenges remain before major Asian or global telecom companies rush into Myanmar. Despite a series of reforms, the country remains plagued by an unpredictable legal system, political uncertainties, as well as inadequate electricity, transport and other infrastructure.

In a statement, Myanmar regulators said they plan to issue licenses that are renewable after an initial term of 10 to 20 years. The licensees will have to meet population and geographical coverage targets, such as servicing the country’s large rural population. Licensees would also have to share infrastructure and commit to offering low initial subscription fees.

Telecom companies have until Jan. 25 to express official interest, and a state panel will review submissions. The government said it would award the licenses on a competitive basis. It wasn’t clear whether more licenses may be issued.

Already, several foreign telecom companies have signaled interest.

Malaysia’s Axiata Group Bhd 6888.KU -0.15% . will notify the Myanmar government of its interest, a company spokeswoman told The Wall Street Journal. Vietnam’s two largest state-owned telecom companies, Vietnam Posts & Telecommunications Group and Viettel Group, are also keen on investing in Myanmar, company officials told the Journal.

Norway’s Telenor Group, which dominates the market in Norway and already has operations in Bangladesh, India, Pakistan, Malaysia and Thailand, also signaled interest in Myanmar. In a statement to The Wall Street Journal, Telenor Group said the market was “an interesting opportunity,” and that the company “needs a clear, stable and investment friendly regulatory framework” before deciding whether to bid for one of the two licenses.

Jamaica-based Digicel Group, whose mobile phone services are available in 31 countries, previously indicated it would bid for a telecom license in Myanmar.

Analysts have also flagged Singapore Telecommunications Ltd. Z74.SG -1.16% —Southeast Asia’s largest mobile operator by revenue—as a likely front-runner in the competition for Myanmar’s telecommunications licenses. Officials from the company, majority owned by Singaporean state-investment company Temasek Holdings, visited Myanmar last year as part of a government-led business entourage. A SingTel spokeswoman declined to comment on Myanmar’s invitation.

Myanmar’s nascent telecommunications sector is considered one of the most promising and potentially lucrative industries in the country. Access to even basic communication remains scarce—just about 26% of the population had access to electricity in 2011, while only 1.26% had access to a fixed telephone line, according to the Asian Development Bank, which believes the sector is “in urgent need of investment.”

Deloitte, in a report published mid-2012, estimates that Myanmar needs to install thousands of kilometers of fiber infrastructure and more than 15,000 towers by 2015—costing about $4 billion—in order to provide coverage to meet its targeted levels of telephony penetration.

Telecommunication services are also expensive and out of reach to most Myanmar citizens, with call rates at $0.60 per minute—compared with $0.05 in Thailand—and SIM card registration fees setting a mobile user back between $150 and $350. SIM cards are issued by the Myanmar government, which hasn’t explained the high prices of the chips.

Only 5.4 million out of Myanmar’s 60 million people had a mobile phone subscription as of the end of 2012, translating to a mobile penetration rate of 9%, according to official estimates. This compares with 70% in Cambodia, 87% in Laos and over 100% in Thailand, according to the International Telecommunication Union.

The Myanmar government wants to increase the percentage of the population owning a telephone to between 75% and 80% by 2015 to 2016. It expects to pass a new telecommunications law by June aimed at liberalizing the historically state-controlled sector.

Among challenges, Deloitte analysts have warned of an unstable regulatory framework for investors and believe the current climate for investment in telecommunications infrastructure to be “risky” with “threats of civil unrest and corruption.”

Nicholas White, a client director at Deloitte Southeast Asia, added that “foreign operators face operational risk associated with a lack of telecoms engineering skills in the country” and may not be able to build “ubiquitous access in both cities and rural areas”—one of the demands of the Myanmar government—because it might not be profitable.

Myanmar has long kept a tight leash on the telecommunications sector and kept foreign competitors out of the market. The country’s former military government—which ruled from 1962 before handing power to a quasi-civilian administration in 2010—was suspicious of foreign involvement in sensitive sectors such as communications, and largely insisted on running phone services itself, though foreign companies at times sold equipment there and local companies have begun providing some services.

Over the past year, the government has seen some success in its bid to court foreign investors.

This week, Taiwan’s HTC Corp. 2498.TW -1.20% said that it would be taking its smartphones to Myanmar, hoping to cash in on the growing market, which still remains dominated by cheap handsets. Rival handset makers Samsung Electronics Co. 005930.SE -2.58% and Apple Inc., AAPL -3.15% along with low-cost Chinese manufacturers ZTE Corp. 000063.SZ +2.71% and Huawei Technologies Co., have also taken their wares to Myanmar, so far relying on local carriers Myanmar Posts & Telecommunications and the smaller Yatanarpon Teleport Co. for connectivity.

—Jason Ng in Kuala Lumpur and Vu Trong Khanh in Hanoi contributed to this article.