Você não pode.
Se o seu computador foi formatado, os arquivos necessários para buscar o histórico não estarão mais lá, a menos que você use algumas ferramentas forenses para "desfazer a exclusão" dos arquivos. Isso pode não funcionar, pois é possível que os arquivos já tenham sido sobrescritos. Você pode tentar usar essa ferramenta para restaurar seus arquivos db do Skype localizados na pasta %userprofile%\appdata\ .
Você também pode enviar a unidade para um especialista em recuperação de dados (geralmente começa em cerca de US $ 500 a US $ 700) para ver se os dados podem ser recuperados profissionalmente.
O Skype não mantém o histórico de conversas em seus próprios servidores, portanto, não há como entrar em contato com eles para recuperá-lo.