MOBILE TELESYSTEMS PUBLIC JOINT STOCK (MBT) 20-F 2017 FY Annual report (foreign)

Exhibit 4.258

FEDERAL SERVICE FOR SUPERVISION IN THE SPHERE OF TELECOM,

INFORMATION TECHNOLOGIES AND MASS COMMUNICATIONS

LICENSE

No. 101248 dated July 25, 2012

To render

data communication services
excluding data communication services
for the purposes of voice data communication

This license has been granted to

Public Joint Stock Company

“Mobile TeleSystems”

Legal Entity (Individual Entrepreneur) Primary State Registration Number
(PSRN/OGRN, OGRNIP)

1027700149124

Tax Identification Number (TIN/INN)

7740000076

Principal place of business (residence):

109147, Moscow, Marksistskaya St., 4

The territory of the services is specified in appendix hereto.

This license is valid through:

July 25, 2022

This license is granted based on the decision of the licensing authority - Order No. 724 dated July 25, 2012

This license has an appendix which is as an integral part hereof and executed in four sheets

Deputy Head (signature) O. A. Ivanov

Official seal:

MINISTRY OF TELECOM AND MASS COMMUNICATIONS OF THE RUSSIAN FEDERATION

FEDERAL SERVICE FOR SUPERVISION IN THE SPHERE OF TELECOM, INFORMATION TECHNOLOGIES AND MASS COMMUNICATIONS

PSRN 1087746736296

CN 036948

Appendix to License No. 101248

Licensing Requirements

1.Public Joint Stock Company “Mobile TeleSystems” (the licensee) shall keep the term of this license.

Short company name:

PJSC “MTS”

PSRN 1027700149124

TIN 7740000076

Principal place of business:

109147, Moscow, Marksistskaya St., 4

2.The licensee agrees to commence the provision of communication services hereunder on or before June 1, 2013.

3.The licensee shall render the data communication services for the purposes of voice data communication hereunder in the entire territory of the Russian Federation, using the above radio electronic facilities of the LTE standard and its subsequent modifications, in any of the radio frequency bands: 720 — 727.5/761 — 768.5 MHz, 798.5 — 806/839.5-847 MHz, or 2,540 — 2,550/2,660 — 2,670 MHz.

4.The licensee shall make the following available hereunder to the subscriber and/or user*:

a) access to the communications network of the licensee;

b) connections through the licensee’s network based on the radio-electronic means of the LTE standard and its subsequent modifications; and

c) access to data communication services rendered by other communication operators whose data communication networks interact with the licensee’s communication network.

5.The licensee agrees to render the services hereunder in accordance with the rules for the provision of communications services, approved by the Government of the Russian Federation.

1

6.The licensee shall comply with the rules for connection and interaction of the communications networks, approved by the Government of the Russian Federation.

7.This license has been issued following the results of the open competitive tender No. 1/2012 for the right to obtain licenses for carrying out of activities in the sphere of communication services.

7.1.The licensee shall provide technical capability for the provision of communication services on the basis of its own network based on radio-electronic facilities of the LTE standard and its subsequent modifications, in all localities numbering 50,000 people and above.

In this case, the communication services shall be provided in all secondary and higher educational institutions located within the boundaries of the above localities.

The communication network shall be deployed in any bandwidth assigned to the licensee, as referred to in paragraph 3 hereof, or in any combination of such bandwidths.

7.2.The licensee shall provide the deployment progress of the network of the LTE standard and its subsequent modifications in the territory of the Russian Federation, no less than the following.

Date	Number of constituent territories of the Russian Federation to have a technical capability for the provision of communication services using radio- electronic facilities of the LTE standard and its subsequent modifications in accordance with licenses for operations in the field of communications services, obtained by the licensee following the open tender No. 1/2012.
December 1, 2013	7
December 1, 2014	14
December 1, 2015	22
December 1, 2016	33
December 1, 2017	50
December 1, 2018	60
December 1, 2019	The entire territory of the Russian Federation

7.3.The licensee shall provide data transmission from user stations to base stations at maximum loading of the communication network of the LTE standard and its subsequent modifications at the speed rate of 4 Mbit/s and above.

7.4.The licensee shall provide financing of at least 15 billion rubles per year (starting with the first year as the date of the decision to grant this license valid through

2

December 1, 2013, and further - each calendar year) for operations required to deploy the communication network of the LTE standard and its subsequent modifications, until the complete performance of requirements specified in paragraph 7.2 hereof.

The size of financing specified in this paragraph shall include the licensee’s expenditures for the deployment of the communications network based on radio electronic means of the LTE standard and its subsequent modifications, for the purposes of rendering communication services of the LTE standard in accordance with licenses for operations in the sphere of communication services, obtained by the licensee following the open tender No. 1/2012.

7.5.The licensee, when carrying out organizational and technical measures for the release of the radio-frequency spectrum, shall operate in accordance with Appendix 4 to the decision of the State Commission for Radio Frequencies No. 11-12-02 “On the Radio Frequency Spectrum Used by Radio Electronic Means of LTE Standard and Its Subsequent Modifications” dated September 8, 2011.

7.6.The licensee shall suspend rendering of the communications services in the communications network using radio electronic means of the LTE standard and its subsequent modifications, in the period of organization and conduction of the XXII Winter Olympic Games and the XI Winter Paralympic Games of 2014, between October 1, 2012 and December 31, 2014, in the entire territory of the Krasnodar Region.

8.        ��    The licensee, when rendering the services hereunder, shall abide by the terms set for the allocation of radio bands and assignment of radio frequency or radio frequency channel.

9.The licensee shall have a network management system of its own, which meets the network management regulations established by the Federal executive body in the sphere of telecommunications.

10.The licensee shall meet the requirements for communication networks and facilities, established by the Federal executive authority by agreement with authorized government bodies engaged in the special investigative activities, for the purpose of carrying out of such activities and other measures to prevent the disclosure of organizational and tactical methods of such activities.

3

11.The licensee is not a universal service operator. The licensing requirements are not specified for the provision of universal services subject to universal service contracts concluded with the authorized executive body.

12.The licensee shall provide information on the calculating basis of the mandatory deductions (non-tax payments) to the universal service reserve in such manner and form as established by the Federal executive body in the sphere of telecommunications.

*The services rendered hereunder may be accompanied by other services technologically and inseparably associated with local telephone services, excluding local telephone services using payphones and shared-access facilities and aimed at increasing their customer value, unless it requires a separate license.

4

Laced, numbered and sealed

3 (three) sheets

Head of Department, Maintenance of Registers of Radiofrequency Assignments and Telecommunications Licenses

(signature) I. Yu. Zavidnaya

AUG 3, 2012

Official seal:

MINISTRY OF TELECOM AND MASS COMMUNICATIONS OF THE RUSSIAN FEDERATION

FEDERAL SERVICE FOR SUPERVISION IN THE SPHERE OF TELECOM, INFORMATION TECHNOLOGIES AND MASS COMMUNICATIONS PSRN 1087746736296

065368