In a statement, the company said Paulin was formerly chief executive of Neuf Cegetel, where he led an IPO, Méditel (now Orange Maroc) and SFR.
The "smart cloud" plan aims to consolidate OVH’s role as an alternative leader in cloud and plan will be revealed at the OVH Summit on 18 October.
OVH board chairman Octave Klaba said: “With the benefit of his experience and his leadership, Michel Paulin will help us to accelerate the implementation of our new strategic plan - with him as CEO and myself as chairman of the Board.
Paulin said: “It is a great honour for me to join OVH. I am looking forward to lead this team of 2500 women and men on four continents, with its strong and unique culture of innovation at the service of its clients.
"I am delighted to work with Octave; everyone knows his vision, his entrepreneurial strength and his great humanity.”
Klaba took on the role of chief executive in February 2017 to implement a "next level" plan during which OVH acquired vCloudAir from VMware, created 12 new data centres and introduced a cloud product and services strategy.