The underground development will enable the centre to stage large-scale exhibitions, banquets and sporting events with seating for up to 1,500 people. It is expected to generate £30 million a year.
As part of the deal, developer Cala Morrison will build a 1,500m2 office and retail block on a vacant car park next to the centre in Morrison Street.
It will take two years to complete the extension, which would be owned by Edinburgh City Council and leased to EICC. EICC chairman Andrew Scobbie said: "It will be a terrific boon for the city. As well as extending the space, it will mean the centre is far more flexible."